I don't know why they call it that...
With traditional voicemail, you have to call a number (sometimes your own, sometimes a number provided by your carrier; it is often setup as a speeddial number like "1") and go through a series of prompts to listen to your messages. Typically in the order in which they were received.
A Visual Voicemail app automatically downloads your waiting messages as simple audio files and prompts you (with a system notification) when one or more are available. You open the app, choose which voicemails to listen to - in any order - which to delete, forward, save, and so on. You can even forward a voicemail via MMS or email to yourself or anyone you choose.