Internal network confusion

I have a little home network, connected together through a Linksys Etherfast Cable/DSL Router (which is connected to my DSL). Two PC's and a Mac, all getting DHCP, happy happy joy joy.

But: I also have a network-capable laser printer (HP Color LaserJet 4500N) and that's where my woes begin. Whether I tell it to use DHCP or assign a specific IP address, I can't seem to address it -- that is, it seems like (I could be totally wrong though) my computer is looking OUTSIDE my internal network to find that IP address on the net somewhere.

Is there an easy way to tell it to look on the local network first for the printer? Or am I simply insane and that can't be the problem? Is there a special IP address I should give it (I seem to recall some IP's reserved for internal networks, maybe that would help)?

Oh, and (sorry about this) both PC's are running WinMe.

Any help would be appreciated. I have a longish parallel cable running to it right now so I can at least print, but that's a lousy long-term solution since the danged thing should work on the network.

Thanks in advance!