What I did, and this is the way I would advise folks to do it assuming you are USA Based and plan to go full bore into the venture, is pick a name and then search on google to see if anything like it exists. If its not unique try something else. Once you get what you think you want to use, go to your state's department of state website and search for business names, as part of the business registration process. Its the part before you pay or submit. Once you confirm that the name is available, I recommend you register the business itself as either a S-Corp, C-Corp, or LLC with the state, then do the same at the federal level. The state you operate in determines which of those is the best and/or most advantageous. If you do this kind of thing often, its easy, but if its your first time honestly working with a lawyer is best to make sure you don't miss a step and you get everything set up correctly. Without an attorney you can expect the cost to be ~ $300 to $600 depending on the state. With an attorney's help it could exceed $1000. Different states have different requirements for articles of incorporation or LLC agreements so thats why an attorney is helpful the first time around. You normally have to file with dept of state in your state, and dept of state federal level, and you have to file separately to set up your business in your states dept of revenue. So there are at least 3 separate filing steps. If its your first time get a lawyer. Trust me its worth its weight in gold and once you do it once time, you don't need the lawyer if you start more businesses because its the same process.
Now if you are a 1 man show and you want to do it on the cheep, there is the Sole Proprietorship option that doesn't require you to do anything other than file a Fictitious Name with your state's department of state. For this, your tax guy can help you because its more of a tax function then a legal fiction. You still have to file three levels (dept of state - state, dept of state federal, depot of revenue - state) but your tax guy can help you the whole way.
SOME tax professionals have the expertise to help you with LLC, C-Corp, and S-Corp processes, so you might not actually need a lawyer. But its good to have someone hold your hand the first time to protect you from mistakes.
When I started my first business back in 1998 I did it as a sole proprietorship. Unless you have employees or need to pay people a certain way you can really remain an sole proprietorship. If you pay via contract you can stay a sole proprietorship. Tax guy is most helpful in completing all the sole proprietorship steps. Use a lawyer for LLC, C-Corp, or S-Corp.
Hope that helps whoever wants to know.