I often hear the word 'Mehudar' used during this time of year to refer to special Lulav-and-Etrog sets. What does Mehudar mean?
There are a number of ways in which hidur is applied to esrog (and acc to the Magein Avraham other mitzvos like seffer torah and shofar as well), all of them enumerated in Shulchan Aruch Orach Chaim siman 656 and the Mishna Berurah there.
The gemara says to add on a third for hidur mitzvah. This is explained either as meaning a third of it's size or a third of it's price. The reason for the opinion concerning size is that we are dealing with an esrog that is the bare minimum size and we are afraid it might shrink, so we get a larger, i.e. nicer, one to avoid this worry. According to this opinion, even if one already bought his bare minimum esrog, he should switch it any time possible to a larger one. The opinion who explains hidur as applying to the price understands the hidur to be na'ah, pretty, in it's more simple sense. The Biur Halacha also mentions that if there is a safeik of psul such as a machlokes if this particular esrog is kosher or not, than everyone agrees to add a third of the price to upgrade to an esrog that all agree is kosher.
Five conditions of a hiddur esrog according to the Tiferes Yisrael Sukkah 3:37 from most to least important.
That it should be completely clean,and especially by the chotem (when the middle starts to bend in) there shouldn't even be pin drop of something unclean.
The esrog should have many bumps and not be smooth skinned.
The ukatz (bottom stem of esrog) should be indented into the esrog that its surrounded by the esrog itself.
It shape should be like a tower (wider on bottom and then narrower on top), and not look like a ball.
The shoshanta (crown on top of pitum) should be completely intact and should be symmetrical with the ukatz on bottom.
Text of Tiferes Yisrael:
Mehudar (מהודר) can be translated as 'pretty', but is generally used to mean 'above and beyond' what is strictly required.
For example, a kosher etrog can be ugly, but there is no problem with using it. A mehudar etrog is a nice one, and generally more expensive also. It's a 'hidur mitzvah' (beautification of the mitzvah) to use a nicer set.
Consider also 'mehadrin' kosher food. It comes from the same root word. A mehadrin hechsher is generally slightly stricter in their observance.