Vector graphics are graphics that are constructed from commands or from math equations, and the graphics can be scaled to any size without effects like pixelation like you get when you, say, increase the size of a bitmap image by 10 times. Vectors can be either 2-D or 3-D.
A really simple example would be a circle. Let's say you have a 320x200 screen and you want a circle to fill up the screen. If this picture is a bitmap (like a gif/jpg/png...) where every pixel is explicitely defined as being on or off, by the time you scale up to a 1600x1200 screen, you're going to see some -major- jaggies on the edge of this circle.
Vector graphics, OTOH, would let you say "I want a circle that fills the whole screen" and the circle is drawn for whatever resolution you're at. Various resolution-independant display technologies have been proposed in the past but none of them have really taken off on the desktop to any real degree...
Pretty much... both Gnome and KDE support SVG for icons. I've found that I love SVG icons, even though I only keep 2 of the 3 default Gnome icons on my "desktop" anyway.
Just for completeness, IRIX[1] has used vector icons for a while, too.
I don't know what format, but it seems they don't support gradient fills, so they're not quite as pretty as the SVGs, but they've been in there since the 90s.
[1] SGIs 4dwm and assorted tools, really, but then again, that is a vital part of IRIX.