For a hosting provider I would suggest first reading through the treads here. I use webhost4life, but can not fully recommend them unless your looking to start the site on the cheap end of the scale. Some of my research indicates PowerDNN.com is a solid hosting provider, but not cheap.
As far as setuping up DotNetNuke, I would simply read the documentation that comes with the installation download. Most hosting providers will have an automated installation process, or will be very helpful in getting DNN setup on your server. I would suggest giving it a try on your local machine first. Come back here if you have question, or run into problems.
Good luck and have fun!