Andante means "with movement" or "moving". The right tempo would be one that facilitates a smoothly flowing, but not hastened melody. As far as exact beats per minute, depending a lot on the style of the music, the period and the composer, andante can be anything from <60 to 90>. Words that indicate tempo are highly subjective. The performer uses what knowledge he has about music in general (along with good ol' fashioned intuition) to arrive at a final tempo.
Of course, that depends on what the definition of final is.