What is the maximum or minimum tire width I can fit on my bicycle
Maximum tire width is dependent on two main factors, clearance at the frame/fork, and the width of the rim.
As for the frame clearance this can usually be visually inspected and easily distinguished if a larger tire than the present tire will cause issues. Brakes such as V-brakes or cantilevers may also cause clearance problems with some tires so attention should be paid to them as well.
Mud or other debris should also be considered for mountain bikes and applications with fenders/mudguards. You should not run clearances so tight that one little pebble caught in the tread will hit the frame, fenders or other parts.
Think of the difference between both sizes you are considering and then split that number in half, that is the distance you will need to be able to clear on either side of the tire at the chainstay essentially. So if there is a 4 mm difference in road tires, the new size will roughly add an additional 2mm onto either side of the existing tire is one way to think about it, but the top of the tire needs to also be checked as the new tire may also be taller in addition to the increased width.
Knobs on MTB tires can also vary greatly and play a part in your decisions and fitment as well. One 2.25&quot; tire may come out to be shorter than another more aggressive 2.25&quot; tire due to the shape and size of the knobs.
As for rim to tire interface there are multiple guidance charts available online that give a rough estimate if a tire is compatible with a certain rim width, such as this one from J&amp;B Importer's, a bicycle parts distributor's catalog.
As an example you can see that a rim width of 19mm (top row) should be compatible with tire width of 28mm/1.10&quot; through 62mm or about 2.5&quot;. But seeing as 28mm is the lower end of that column somewhere in the 2.2/2.35 range would be a safer bet.

However just because it will fit on the rim does not mean it will not rub on the frame so that is what is most important.
For small changes such as from 26 x 1.95 to 26 x 2.125, or 700C x 23 to 700C x 25 you are almost certainly safe from a rim standpoint if the bicycle was factory equipped with 1.95&quot;/700x23 tires.
To be certain, the model of rim should be referenced and the width noted.
Please also note that the same applies to going to a smaller tire size, too small of a tire on the same rim could not seal well and potentially cause flats or blowouts when the tire bead cannot seal against the rim well enough.
Edit: July 2020 - Suggest reading the the answer posted by @Weiwen Ng which contains updated information.