tl;dr
The first mission to run the engines normally at above 100% of nominal maximum thrust: STS-6
The changes to the engine made that thrust increase possible: the 147 design changes implemented between the FMOF and FPL versions of the SSME.
Details
The SSME had five major versions over the life of the program. The definition of 100% Rated Power Level (RPL) changed with each one of them. The most important definition of what 100% RPL means, and the only one consistent throughout the program, is that it is the power level / dynamic balance point attained at the end of the Start phase when the engine enters Mainstage and is ready for flight.
Taxonomy of the SSME
There were five major versions of the SSME
First Manned Orbital Flight (FMOF)
First flight: STS-1 (April 1981)
Main Combustion Chamber (MCC) pressure at 100% RPL: 2960 psi
The FMOF SSME was a de-rated version that was not certified to operate above 100% RPL except in emergency situations (i.e. where doing so might prevent loss of the crew). (For the first mission, even the emergency power level was 100%, but this was raised to 107% for the second and subsequent flights.) Many components had to be replaced after every flight. Used only on the first 5 missions of Columbia.
Full Power Level (FPL) aka Phase I
First flight: STS-6 (April 1983) (first flight to use 104% power level nominally) (First flight of the Orbiter Challenger)
MCC pressure at 100% RPL: 3006 psi
The FPL SSME was certified to operate at 104% nominally. However, the turbopumps still were not reliable enough to allow nominal operation at 109% RPL (which was then considered desireable for some planned payloads) so this power level was only allowed for emergencies (although this last still made people very nervous, and was lowered to 107% on some missions). Major changes from the FMOF included redesign of the powerhead, main injector, and turbopumps.
Phase II SSME
First flight: STS-26 (September 1988) (return-to-flight after the 51-L accident)
MCC pressure at 100% RPL: 3006 psi
Phase II engine improvements included both items coming out of the major safety reviews conducted after the 51-L accident and items intended to improve turbopump life - more powerhead redesign, new high pressure turbopump blades and bearings, and a new main engine controller. However, turbopump life was still unsatisfactory and margins of safety when operating at high power levels were very thin.
Block I/IA SSME
First flight: STS-73 (October 1995)
MCC pressure at 100% RPL: 3032 psi
The major change for Block I was that NASA was unhappy enough with the turbopumps to get Rocketdyne competitor Pratt and Whitney to design a new set of high pressure turbopumps. Block I SSMEs included Pratt's newly designed High Pressure Oxidizer Turbopump along with a number of other significant improvements. Block IA SSMEs had a further main injector modification to improve performance.
Block II/IIA SSME
First flight: STS-104 (July 2001)
MCC pressure at 100% RPL: 2760 psi
Block II SSMEs added the redesigned Pratt High Pressure Fuel Turbopump and incorporated the Large Throat Main Combustion Chamber (MCC). Block IIA was the Large Throat MCC alone. The new MCC allowed a significant drop in MCC pressure (and therefore pressures throughout the system) to provide the same engine performance.
(source - handout I picked up at a Boeing PR event)
Normal Throttle Operations
About six seconds before liftoff, the engines would be commanded to start in a staggered sequence. Start phase always took the engines to 100%. For most of the program, a few seconds after liftoff, they were then commanded to 104%. Around 30 seconds mission elapsed time, they would throttle down to around 67%, and around 30 seconds later, throttle back up to 104%. (This is the thrust bucket referred to in this question) Some missions had two-step thrust buckets where the throttle-down was done in two increments. Late in powered flight, the vehicle would reach its limit of 3g due to propellant depletion, and the engines would start to throttle down to maintain 3gs. When the orbital insertion performance was attained, the engines would be commanded to 67% (if they had not already reached this power level), and then commanded off.
Addendum
Despite all the changes and redesigns, the normal operating point would remain at 104% RPL until the Space Station era, when it was tweaked to 104.5% RPL to slightly increase performance. No SSME ever ran at a power level higher than 104.5% in flight during the history of the Shuttle program.
References:
Space Shuttle Missions Summary
Space Shuttle Main Engine, the relentless pursuit of improvement
Space Shuttle Main Engine, 30 years of innovation
Space Shuttle Main Engine Orientation
Personal notes