1. There are mainly 2 versions, id3v1 and id3v2. v1 is old and has less fields, while v2 is newer, has more fields, and is harder to understand
On windows, I've found that simply using WMP is the most painless way to go. Lifehacker recommends Media Monkey, and others have recommended itunes.
For linux, I use Ex Falso. But most media players (Amarok, Exaile, Sonata, etc) should be able to change the metadata.
2. Album art can be stored in 2 main ways, and many other not so common ways. The first to is to embed the art into the song's metadata. The other is to have it as a separate image file stored in a particular location with a particular name (the same name as the album, in the same directory as it, etc). The second method is usually used by music players because it means they don't have to embed the art. This also means you can't see the art in any other player. Obviously for syncing purposes, the first way is preferred.
Amarok has worked -- somewhat -- for embedding album art. But by far, I've been most successful with WMP v < 11. Whatever you use, make sure the option says "embed art with music" and that you set the picture as "album (front cover)".
In any case, you're better off using WMP because you have a Zune.