3. Employ these words as prefixes and suffixes, and use both standard and non-standard. For example for suffixes, a standard suffix would be something like "-ly". A non-standard would be to just use a word in place as the second half of the name.
4. Mix and match the above multiple times. Create lists of possible names and even those that are a bit crazy. Don't reject anything at this stage - you are bstorming! Put them up on a wall so you can see them all at once. Continue putting words together and creating new combinations.
5. Pick favorites, then throw into a domain name search to see if available. <-- this is usually very depressing - not many domain names are left out there. NOTE: be careful - I'm sure that some people are tracking what domain names people are searching on although i can't prove it. but I'm a paranoid guy ;-). So only check names that you are absolutely sure of because if someone believes you are interested in a name, they may buy it before you and try to sell it back to you.
6. Do informal or formal testing of name against customers, friends, family, etc. Check for unintended or alternate meanings.
Check foreign language dictionaries to make sure your name doesn't mean something you don't want it to mean in another language, ie. Chevy Nova, where nova means "doesn't go" in Spanish.
7. Repeat above until you find a name that you like.
8. After you pick a name, then search your state's database of company names. BUT I would highly recommend that you pick a company name that is completely different than your product/website name. To me, staying stealth in today's world for most startups is critical since things get copied all the time and easily.
9. As for trademarking, you can do your own trademark search at the USPTO website.
You can also file your own trademark application there so i think you can probably get away with not paying a lawyer to do it.
More on general information on trademarks can be found at the USPTO website.
Some online guides to naming: