Spend some money, but not too much. Make it look better than something bought for $5 online, but don't worry about sinking tons of money into branding. After all, Google was "Backrub" once

Depends. You might be able to get some decent stuff from something like Fiverr if you're just looking for a logo.