Feebas evolves into Milotic either by significantly increasing its 'beauty' stat or by trading it while holding a Prism Scale. Both of these triggers for evolution, as far as I know, are unique to Feebas.
A friend of mine has recently started playing Pokemon, starting with Ruby, and aims to fill the Pokedex as much as possible without any outside advice. He was lucky enough to backtrack and find Feebas with little effort but is not using it in his main team.
From my own recollection of Gen. 3, there were never any in-game hints as to how to evolve Feebas. I either found out by looking at a guide or being told by someone else. Is my own recollection of Ruby, Sapphire and Emerald incomplete, or were there really no hints given in the games on how to get Milotic?