I want to recommend a software I've been using for 6-7 years. They recently came up with a new version, and it's the best yet.
It's called Media Monkey: www.mediamonkey.com
It's a great media organizing library, very flexible columns and tags, automatic play lists based on criteria, powerful search and query builder, and lots of other cool features. It really helps when you have thousands of songs, and I can find and pin point songs very fast. It has nice shortcuts to locate relate songs (same genre, BPM range, ratings, ambience, etc...). For example, I can very easily find a "nice slow dixieland blues song but with energetic trumpets" at the click of only a few buttons. It also has VB based scripting engine, and you can define your own scripts, macros or download other open source scripts.
It especially works great in conjunction with a player or a mixing software (like winamp or pc dj), you use mediaMonkey to organize and find your music, and the other one to mix and queue songs up.
It also supports almost all mp3 players (including ipods, with no restrictions!), and knows how to synchronize your computer with them, as well as synchronize your laptop with your desktop (if you have one).
And, it's developed by a small group of developers, with solid user community and no big name interests behind it. It is one of the few softwares I am actually happy to pay for, because I know the money goes directly to the people who been working on it for the past 7-8 years.
There is a free version with basic searching, and a gold version for $20 that has full features.
