I connected an HP Officejet Pro 8500 to an MI424-WR router with a wireless connection. With the router software I can 'see' the printer.
What I can't do is find the printer from both the main PC (direct Ethernet cable connection to the router) or from another PC that has a wireless connection to the router. Both are running XP SP3 (one Home version, the other XP Pro).
Running Firewall software? You might have to see if it is blocking Windows File and Printer Sharing before doing anything regarding the printer.
As pointed out above the Printer won't just "Appear." It needs to be set up. Add the Printer as a network printer, letting Windows detect it on the network (it should be broadcasting it's presence on the network) and add it from there. Otherwise, add the Printer manually by using it's name on the network as it appears in the router to add it. You don't want to add it by IP Address unless the Printer is using a Static IP. The easiest way, though is to find it using "My Network Places" and viewing the Workgroup computers. If the Printer is within the same Workgroup as your two computers, the Printer will show up as a computer in many cases. You should be able to double click on it and connect to it, installing any needed drivers in the process.
After Fios was installed we couldn't print from our laptops. The printer showed it knew our computers since the laptop names were there. We had to delete the printer, make sure it is the right one. We have a choice of USB printer , networked and something else. We deleted the networked printer and then had the computer look for new printer. After it poped it in we were able to print. I guess the setting although changed to Fios setting just didn't take or it was still looking for old router. Who knows but it worked.