FPS is "Frames per second". It determines the performance of games, with a higher rate producing smoother graphics. A low rate will appear laggy/chuggy/slow/choppy and can make a game unplayable as ingame actions take far too long to complete with far too few frames. I would mark 30 frames per second as a minimum for satisfactory gameplay, and 40+ as smooth (different people will have different opinions on this!). ;)
A program like FRAPS can tell you your framerate.