Hmmm, well, I do this for a living and I always start by making a mock up in a graphics program. The site i built for The Unforgiven had to take some things into account. The first being that most visitors would be arriving through the link on this site. This site though retains the header frame with all the links for Aces High, so my palette was chosen for me.
Keep it simple, keep it small (in terms of file size - no-one wants to spend 3 minutes waiting for a webpage to load, keep it classy - music and guff like that takes a long time to download, can often be annoying no matter how much you like the tune and can often get you sued (Don't believe me? I've aleady been to court 3 times thanks to New Line Cinema)