I am trying to find a rough Linux server that I am told is on my network. Anyone have any idea how I can sniff it out? I have never attempted anything like this before and don't have the slightest idea how to do it or if it is even possible.

Thanks in advance!

Errr, rough?

Guess he means he's gotta find some "rogue" server.

What approach you take depends IMHO on what "signs" you've gotten (you don't mention any details). For instance if you received a Black Ice or in other ways automated report, you should archive it carefully in /dev/null and put the sender in your killfilter, but if you've received a CERT, Dshield or other report from, say, someone's upstream ISP, they usually have included hints like ASCII tcpdumps or (IDS/firewall/sys) logs you should be able to work with.
The other dependancies before you work out what to do could include actually *knowing* what's on the LAN. If you don't maintain ingress/egress logs, and if you haven't got a clue about what's happening, and if there's no weird stuff in the DHCP logs, and if these boxen are for workers/drones/humans, you could log everything to/from the LAN (the ingress/egress logs), (and just mail a polite notification and) nmap the heck out of them for starters.
If OTOH you *know* some boxen are servers, and maybe have fragile stuff on 'em that a scan could break, single 'em out and comb 'em over with a slow nmap scan, follow up with a manual audit of the boxen's logs (remote syslog?) and integrity (Aide, Samhain, Tripwire, Chkrootkit, COPS, Tiger, lsat, whatever else). And if you have got a clue which box it is, but not *what* it is running, you could tcpdump everything from/to the box for starters, then parse the tcpdumps tru Snort.