have a look at this website, alot of workers post on there & might be able to guide you-

hhtp://www.faliraki.me.uk/

May is a good time to book your holiday as that's the best time to start looking for work. You're doing the right thing, just book your holiday and ask about in resort for bar/restaurant work.
It's also worth checking the travel agencies that work with the UK tour operators as they'll often take on staff for airport transfers, guiding excursions and in Lindos, see-ins (walking people to their accommodation).
Good Luck

the best way is like marcus says, book a holiday, and then ask around bars etc, then you can stay on after your holiday...but i would get there in may, as june/july all the uni students go out looking for jobs