If you're not on ubuntu then hopefully you can adapt this information for your system, add a comment if you do! For ubuntu I simply needed:
sudo aptitude install gearman-job-server gearman-dev
There should be a running task which is /usr/sbin/gearmand, this listens on port 4730 of localhost by default.
The gearman package in pecl is still in beta (I have no idea why, the documentation seems thin but it does work fine for me), so to install it I had to do:
sudo pecl install gearman-beta
(on Ubuntu 10.10 this worked flawlessly, but there are known issues on earlier versions where make fails due to an old version of libgearman - see the pecl bug for more information)
At this point, everything is set up and I could start using Gearman - I will write more about my experiences as I have them.