Yes, your hosting will need to have a MySQL database. Also, there are some other minimal technical requirements in order to run Concrete (you can find this info in the 'Documentation' area on this site).

Personally, I recommend InMotion Hosting. Get their Business Class hosting. It's super-fast, and they have excellent support.

TIP: Any host you go with will have certain limitations. One important thing to consider is the "PHP File Upload" limit, as Concrete has file uploads. Try to find a host that allows at least a 10MB file upload limit. The business class hosting for InMotion has a 128 MB limit (which is PLENTY)!

OR... I can host it for you! I can set you up with your own hosting back-end administration (Cpanel). If interested, send me a private message.