Evolving Feebas is also incredibly unique and still stumps many a trainer, Feebas evolves via you maxing out it's Beauty Contest Stat out. The way you do this is via the following. First off, to ensure that you can do this catch a Feebas of any of the following Natures:
Modest
Mild
Rash
Quiet
Next step is to blend some Berries, either with your friends or with the people in the game. I suggest using the Ganlon Berry as it will give you the most punch even if you do poorly while blending. However any Blue or Indigo Pokéblock will raise the Beauty stat the best aswell as others that were blended with your friends if you use a Dry berry.
Go to the Contest Hall and blend the Berries and thus feed the Feebas the Pokéblock or Poffin. Once you've fed it enough, you should get a chart in the Condition part of your PokéNav/Status Screen that has the Beauty peaked such as in this picture to the right, other stats can be high but they are irrelevant to this.
The stat can be peaked without the Pokémon being full so you may be able to train your Feebas or Milotic in other contests too, you will know when it's been peaked when it stops saying it has been raised when you feed it Pokéblocks/Poffin. This step obviously can only be done on Ruby, Sapphire, Emerald, Diamond, Pearl & Platinum.
The next step is to level it up to the next level so it can evolve. This can happen on any of the games since the stat details are saved so you can trade it to FireRed, LeafGreen, Colosseum or XD if you wish to evolve it on those games, just level it up in battle or use a Rare Candy and boom, your Feebas will start evolving.
Alternatively, in HeartGold & SoulSilver, the massages that you get from Daisy Oak in Pallet Town and the haircut brothers in Goldenrod City will boost your Pokémon's Beauty stat by 22 Points per massage. After 8 of these massages, your Feebas will be at the point to evolve. Luckily, this method is not affected by nature so you'll be able to get whatever nature Milotic you want.
This is what I found on Serrebii.net:
http://www.serebii.net/games/feebas.shtml
Hope this answers your question!
