In general, VBR is variable bitrate, which means that each mp3 frame may be of a different bitrate in order to optimize sound quality and storage space. A frame that can be compressed more without sacrificing (much) sound quality will be, whereas difficult-to-compress frames may have thier bitrates set quite high.

ABR is average bit-rate. It produces a VBR file that tries to make the average of all the frames' bitrates be equal to something. Unless you specifically need a specifically-sized file, I'd not do this, as it's not as well optimized as generalized VBR.

Creting VBR files, though, will produce a file of an unpredetermined size. It'll use as much space as it feels is necessary to make the recording come out at the quality you specify.

The -old and -new appellations are just there so you can use their old and new algorithms. Everyone suggests that the new algorithms work better, so I don't see why you'd want to use the old ones. My thought is that they didn't want to remove stuff from lame, so they just renamed it when implementing the new algorithm. It has nothing to do with the files being inherently different, though; it's just a different method of getting there. (The output will be different, as though it was compressed using two different utilities, each using VBR, though.)