Ah, the most difficult part of setting up a server. People won't join if it's uninhabited, but it's uninhabited if people don't join. Catch-22 in it's best form.
Getting the initial feet in the door is probably the hardest bit - rather like starting a new SE site - once the critical mass is there then your server will be (mostly) self-promoting, or at least self-sufficient (self-sufficient in terms of activity).
Getting them online
Much like trying to 'get the girl', there are several ways you could start out, some not so great (chloroform/passing other people's creations off as your own), others much better (using infinite reserves of charm and wonderfully good looks & personality/sites where the intended purpose is server advertising).
There are quite literally a myriad of sites that focus on Minecraft, some new and some well established, that are all trying to capitalise on the insane Minecraft traffic going around right now (Minecraft Wiki & Forums combined currently serves more traffic than SE). You need to work out where you time is well invested and where you will be wasting it.
Whack your server on as many sites as possible, and don't hang back. In your 'advert' you are looking to summarise the essence of the server as quickly as possible in the introduction, followed by any relevant information people should know if they're thinking of joining your server. Unless you're running an RPG server, where people really (kinda) do need to know all your rules and groups before they join, don't fill your 'ad' full of bullshit, you just want to get them on your server.
Important things to reference:
- Creative/PvE/Survival/War/Bizarre Hybrid, etc. - in a word, how is your server generally classified?
- Whitelist? - Do you have a whitelist? Will players need to make an application? For gods sake, don't make people beg to join your server. That will put anyone above the age of 15 right off. (Unless, of course, you have some epic creation)
- Protection? - how are your players creations protected? I'd be pretty pissed off if I invested time in a server and then a griefer came along and destroyed my creations with no backups/rollback/area protection
- IP/Domain - for obvious reasons
- Plugins - but only list the ones 'regular' players have access to and that will enhance their gameplay - if you run a creative server it may be worth stating that players have access to Magic Carpet, for example
Things not to reference (well, in my humble opinion):
- Server specifications - I don't care if you're running on super-duper hardware, as long as I can play smoothly.
- Donations - People will not want to donate before they've been on your server, so don't mention it in your advert. In-game is a much more appropriate place to ask for donations.
Having said that, here's some sites you can advertise your server on:
Build something awesome (not just average) and post it around. Some sites may consider it blatant advertising if you spam the address along with the post, some will not. If it's impressive enough the users of the site will usually ask you for the IP regardless.
Some sites you will have to approach to get your project in there, some will allow you to post freely.
Some places to get you started:
Also make sure to use a custom texture pack, preferably as obscure as possible, it is guaranteed that at least one person will ask what texture pack it is, starting some level of activity in the comments
Offer something unique
There's another way of drawing attention to your server, and that's offering something nobody else does. Now I can't tell you what that 'something' should be, that's for you to think over, but it should be enough that people play because your server offers something they can't get elsewhere - be it a specific play style or custom mod.
Keeping them online
(once|if) you do get people connected to your server, you haven't finished yet. It's not enough to get them to join once if they never come back. Your server needs to be like a drug dealer - get them hooked and keep them there.
First impressions count. Spawn is an incredibly important part of keeping new players connected.
Teleport yourself to your spawn and look around. Does your server look inviting when player connect? Is spawn itself impressive? There should be some effort put into it making it look good.
There are certainly several things you don't want around your spawn. Unfinished projects, phallic constructs and obscene signs/block lettering are such examples. These should be destroyed with fire.(A pickaxe is fine too)
Spawn doesn't have to be fancy but it certainly shouldn't look bad.
There should be at least some instructions of how to get started, either via. chat or through signs. If it's creative, how do I give myself items? How can I get an area protected?
If someone new connects while you're online, say hello. Introduce yourself, ask if they want a tour/need any help, then offer information if it's requested. Don't overwhelm the new player.
If a new player starts a project in their first playing session, they will likely come back. At this point, congratulate yourself, then rinse and repeat until you hit critical mass.
You're not going to attract new players without putting some effort in.