If it's a new name, (since you said register and not renew) it really doesn't matter. If you don't know the nameservers, you can save a tiny bit of time by signing up for the hosting first and obtaining your nameservers to specify during the registration process. Domain propagation is your bottleneck anyway.
It definitely matters. If your domain name is nice to remember and somehow popular, you may want to register and reserve the domain first. Secondly, to host it, you need a domain. Well, you can do it without a domain name initially, but it will cause you twice the trouble going through the domain and hosting registration process.
It would be best that you register the domain first, and then host it with the hosting company you choose to sign up with later.