There are 2 routes you could go on this. When your site is really big, then you'd definitely be looking at some type of VPS/Dedicated hosting. So the 2 options would be to go with a beefy right out of the gate, or go with something a bit more moderate and move up to a larger plan as your site grows.
The second option is what most people do. They'll start with a smaller hosting plan and then move to something bigger when it's needed.
You'd need to have your hosting purchased in order to install UBB, as it will need to be installed on the server, so you'll want to get that taken care of.
Not really much required beyond that. Who you choose for hosting is probably the toughest part. There are so many different providers available and everyone has different experiences with them.
Some that seem to popup quite a bit are webintellects.com, hostgator.com, godaddy, lunarpages and a couple others.
