In which case, look for hosting that provides;

• MySQL Database
• PHP (version 4 or 5)
• Apache Web Server with mod_rewrite enabled
• Linux

You might need to contact them in order to find out some of the information above (particularly mod_rewrite capability).

Are you looking at UK, US or elsewhere hosting?

WESH could provide everything you need if you're after UK hosting.

Otherwise, scroll through our hosting forums - there's plenty of threads discussing particular hosting companies.