Carefully... and with a lot more detail than you've given
A few questions to ask:
Monthly budget?
One site, or several sites? WP Multisite?
Is SSL required?
Traffic (average per day/month, max per minute/day/hour/month)
Uptime requirements?
Is the site easily cacheable (publishing/blogging), or highly dynamic (logged in users, web app)? Ideal caching type (plugin, Varnish, object caching, memcache, redis)?
Support needs (24/7, phone, email, chat, dedicated support rep)?
Level of technical savvy - or how much do you want the host to manage (bare bones server, VPS, all the way up to WordPress, WordPress as well)?
Do you need a single site hosted, or a dev, stage, and live environment?
Will deployment be handled by via FTP/SFTP, or Git push?
Geographic location of majority of users?
Political and/or governmental concerns (EU Privacy laws, etc)?
HIPAA compliance required?
Built in CDN, or BYOCDN?
Theres a few more, but these are the primary questions I ask when choosing a host for a client.