There are lots of different approaches to advertising Minecraft servers, this is a list of some of the best.
Server lists are websites that rank Minecraft servers in order of popularity, which is often calculated by the number of votes a server gets. Some of the more popular ones get tens of thousands of views every day, so having your website high up on one of these sites by getting lots of votes will get you lots of views. For a list of the top server lists, take a look at this tip on What are the best Minecraft server list websites to use?.
YouTube is a great way to advertise your server. All you need to do is create a YouTube channel, and post video related to your server. So things like let's plays, tutorials, cinematics; things like that. Mention occasionally that you're recording on your server and give the IP, so when people watch the video they're encouraged to join. Also put your IP in the video description. If you post videos every few days and promote those through things like forums, you can get a lot of traffic, very quickly. Aim to record videos related to popular game-types like parkour and dropper. An example of a channel of this type is Simo389.
Twitch is a website where you can livestream yourself playing on your server in real time to potential players. By displaying the server IP in the top of the stream, viewers can immediately join if they enjoy the stream. By picking a popular game mode or running things like build competitions you can pick up viewers very fast, but you need to stream for a few hours at a time for this to be effective - and make sure you interact with your viewers! Head to the Minecraft section on Twitch to see some examples of current Minecraft streamers.
Minecraft Forums are an alternative to server lists, targeting a slightly different audience. To advertise on one of these, you just need to go to the servers section, post a new thread about your server with a short title; in the content your server/website IP, a short description summarising what players can do on your server and a few good screenshots/a video (or both). So anyone scrolling through the forum will see your post and if they like what they see will check it out. A few popular ones are Minecraft Forum and Planet Minecraft.
Reddit is very popular at the moment with gaming, so is an easy way to get lots of traffic for your server. All you need to do is post your server under the Minecraft servers subreddit at /r/mcservers. Note: You must follow the subreddit rules, or your post is automatatically deleted.
Something to note is that it's often effective using unpaid advertising than paid, as when you stop paying often traffic stops immediately, whereas unpaid advertising continues indefinitely.
Project Wonderful is a system that allows you bid for ad spots on specific websites in intervals of 24 hours. So you'd bid say $30 (this site only deals in dollars) for your ad to be displayed on website x for 24 hours, with a maximum budget of y. It also allows you to specify which region to display it in, so is great if you want to target certain countries. You just need to register on their website to get started, and follow their instructions.
Pay YouTubers to record videos on your server. This is an approach that's used fairly often, but not well known. To do it, all you need to do is find a Minecraft YouTuber and send them a message on their channel or via email if they provide it offering them something to record a video on your server. Offering money is a sure way to get their attention, although be aware that very large YouTubers with millions of subscribers expect amounts of £500+, as they get these sorts of messages often; a good idea is to find smaller YouTubers with around 50k subscribers, as you're far more likely to get a reply and for a much cheaper amount (around £50-200 per video). You can also offer for example a free rank on your server, or their own whitelisted server on your network for a mini-game to record on. Just think of something that they might be interested in. Here's a useful list of Minecraft YouTubers you can approach, and another here with how much some of them charge.
YouTube Video Ads. YouTube has something called AdWords, which as well as text ads allows you to post video ads which are played at the start of other YouTubers' videos. All you need to do is record a video promoting your server, preferably less than a minute long and with a catchy 5 seconds at the start to get viewers' attention, then create an ad on AdWords to start promoting it. You can get views for roughly 1p each, so £1 for 100, etc. This can be a pricey option when compared to others, so be very careful to only spend say £2 a day on this initially to see how things work and what sort of engagement you get. That first 5 seconds is very important to get viewers to watch the whole ad.
Twitter/Facebook Ads are another option to reach a much a massive user base of lots of different ages and interests. Both of these are useful in getting traffic to websites, so you can aim users to your server website and then to your server itself. Facebook is less effective recently, as it has a very low engagement rate for users; whereas Twitter has a much higher engagement per view.
Simo389 has been running Minecraft servers since 2012, and developing for them since 2013. Currently he runs MineRifts, a YouTube channel and shares advice in these tips on how to publicise & improve your own Minecraft server.