Yes, the sensors are battery powered, but the battery cannot be replaced. You'll destroy the sensor trying to open it to get at the battery.
TSB PG004-06 says that the sensor "is equipped with a lithium battery that has an average life span of 10 years."
To the OP, the dealer should have been able to be a little more exact than "they're all messed up". Each sensor (all 5 - the 4 wheels plus the spare) has a unique ID number that the computer has to recognize. When a new sensor is installed on the vehicle, the ID number needs to be programmed into the on-board computer. When the tire pressure light is flashing, either for the first minute after starting the car or constantly, then it has stored an OBD code explaining the problem. If the problem is that one or more sensors are missing, then the issue could be bad programming, a broken sensor, or a dead battery.
If the light is on solid as soon as you start the car, the first thing to do is check that every tire including the spare is well above 27 psi. This winter, my light came on because the spare got too low when it was really cold out. Even though it came back up to 28 psi on its own as the weather got better, the light was still on. Filling it to 35 psi got the light to turn off almost immediately.
The system won't tell you which tire is which - it just knows them as #1 through # 5. Using Toyota's scan tool, it's possible to get the pressure readings. So, to identify which tire is which, the tech should simply let air out of each tire one at a time and watch the scan tool to see which one changes pressure.
