Do tubed tires fit all rims, or is there anything I should watch out for?
If it's 25 years old, it's a tubed tire. 26x2.125 is a very standard MTB tire from that era. If you get any MTB 26" tire in the 2.2 to 1.5 in range that should work just fine on your bike. 

For any tire made in the last 20 years there should be an ETRTO number on it as well, this is a number like 50-559. Its' designed tire width and rim diameter. So 26 x 2.125 would be 26 inch ( or 559mm ) rim and 2.125 inch width ( or ~55mm width).

I would put some money in your budget for new tubes as well. 

For more on tire sizes check out Sheldon Browns Tire Sizing Guide