Steinkuhler attended the University of Nebraska, where he won the Outland Trophy, given to the nation's top offensive lineman, in 1983. This marked the third consecutive time a Cornhusker had won the award as Dave Rimington had won back to back Outland Trophies in 1981 and 1982. Steinkuhler also won the Lombardi Award in 1983, marking the second consecutive year a Nebraska player had won that award as Rimington had also won the Lombardi in 1982. Nebraska is the only team that has had consecutive winners of both of these awards. Steinkuhler is one of eight Nebraska winners of the Outland Trophy and one of five Nebraska winners of the Lombardi Award. Nebraska players have won nine Outland Trophys overall, by far the most in the nation. Oklahoma has the second most with four. He is, along with fellow Nebraska Cornhuskers Rich Glover, Dave Rimington and Ndamukong Suh, one of only thirteen players to have won both the Outland Trophy and the Lombardi Award. In 1999 Steinkuhler was selected to the Nebraska All-Century Football Team via fan poll and was named to the All-Century Nebraska football team by Gannett News Service. He is one of only sixteen Cornhuskers to have his jersey (#71) retired by the team.
Steinkuhler is also remembered for being the player who picked up quarterback Turner Gill's intentional fumble in the 1984 Orange Bowl and ran it 19 yards for a touchdown in a play dubbed the "Fumblerooski".
In 1999 Steinkuhler was selected as an offensive guard to the Walter Camp Football Foundation College Football All Century Team. The other offensive guards selected were John Hannah of Alabama, Aaron Taylor of Nebraska, Brad Budde of USC, Will Shields of Nebraska and Jim Parker of Ohio State. Steinkuhler was one of six Nebraska Cornhuskers selected to this team; the others being Rodgers, Rimington, Shields, Frazier and Taylor.
Steinkuhler is one of 54 players and one of five Cornhuskers named to both the Sports Illustrated and Walter Camp All-Century teams.
Steinkuhler was the second overall pick in the 1984 NFL Draft, taken by the Houston Oilers. He was an Oilers co-rookie of the year. He played both offensive guard and offensive tackle with the Oilers after playing solely offensive guard in college. He played eight seasons with the Oilers (some of those alongside fellow former Husker teammate Mike Rozier) before retiring in 1991.
Steinkuhler hailed from Burr, Nebraska, which, according to the 2000 census, has a population of just 66 people. It is thought to be the smallest town to ever produce an All-American. He played eight-man football at nearby Sterling High School. His sons Ty and Baker have followed in his footsteps. Both are defensive tackles and both graduated from Nebraska. Ty and Baker played at Lincoln Southwest High School and Syracuse-Dunbar-Avoca High School.