On the Web Developer Juice blog there's a new post that'll walk you through the installation and integration of the Apache ActiveMQ messaging service and how to integrate it with your application.
Apache ActiveMQ is one good option for implementing message queue in your PHP application. It can be easily installed on your server and it's web accessible admin interface really makes administrator's life easy. It can be easily connected with PHP via STOMP. I will suggest to use MySql for Data persistance and start ActiveMQ as unix service.
Their eleven step process includes getting the packages you'll need to run ActiveMQ, starting/stopping the service, setting up the STOMP transport connector and finally connecting it to MySQL. You can then install the PECL extension for STOMP and reload Apache to get it all working together. They even include a sample script to get you started.