I am using Beanstalkd, it is small and fast and you just apt-get it on Debian.
However, I have noticed that oftentimes devs are using queues where Workflow Engines would be a better fit.
If your message processing time is in tens of seconds – talk to your local Workflow Engine professional (: