You never said anything about what sorts of music you want to DJ and what your functionality requirements are (cross-fading? beat matching? pitch bending?).

If all you want to be able to do is cue up multiple songs without any kind of cross-fading, then just about any MP3 player will do the job. If you want to preview on headphones while playing something else to the house, then something cheap like a Griffin iMic can provide you a second audio out. That's actually all I ever need. I configure Winamp to play to the iMic and use that for the house, and I use iTunes through the built-in audio out to preview stuff. I imagine you can do something similar with any two different MP3 players on Linux.

Now, if you want fancier mixing and whatnot, Google for "open source dj mixer", which turned up Mixxx and also helped me find OpenJay, which seems to be dedicated to exactly your needs. There's even a tool called xwax, which understands timecoded vinyl for scratching and so forth. Lastly, you might want to check out UltraMixer. It's not free, but it is cross-platform.