The Linksys WRT54GS v1.0 board has a DC/DC converter which converts the 12V down to 3.3V needed for the router hardware. The DC/DC converter is the 5pin little SMD part near the electrolytic capacitors (shown in the red circle in the image below). It is the AC1501-03 from Anachip Corp., an integrated 150kHz step-down switching regulator with thermal and over-current protection. It works with a supply voltage between 4.75V-40.0V and gives a stabilized 3.3V @ 3A.
That means that the lower limit of the supply voltage is about 5V but the upper limit is much less than 40V. That's because the input capacitor is rated at 25V, so I would not suggest running it on more than 20V.
I connected a variable power supply on my WRT54GS to take some measurements and here are the results. Unfortunately the power supply I used (Agilent E3620A) has current limit at 1A so I couldn't go below 6V. During the test the router was idle.
No need for a Power over Ethernet kit!
Worst case scenario: If you have 100m of ethernet cable (UTP cat5e 24AWG) going to your router and give 12V using 2pairs, there is a voltage drop about 5V across it. That means that there are 7V at the other end which are enough for the router to work ;-)
Differences between hardware versions
As far as I know the WRT54GS v1.0 and the WRT54G v1.1 use the same voltage regulator. I am not sure for the other hardware versions so before trying anything of the above, open your router and check it.