Gregory's first coaching job was at Iowa Central Community College, where he was assistant head coach and athletic director of the new football program. In Gregory's three years there, the program had a 24–3–1 record and won the Wool Bowl in 1969. John Matuszak, who was recruited by Gregory, went on to become the number one pick in the 1973 NFL Draft. His first college head coaching job was at South Dakota State, where he had 55–50–3 record from 1972–1981. Gregory is third in school history in coaching victories and his 1979 team had a single season best record of 9–2. SDSU didn't have a winning record the previous 11 seasons before Gregory's arrival. After serving as Northern Iowa offensive coordinator in 1982, Gregory was the offensive line coach of the Winnipeg Blue Bombers for the six seasons. In 1984 Winnipeg won the Grey Cup in part due to Gregory's offensive line that helped set a CFL single season rushing record.
After the 1986 season he was hired to coach Saskatchewan Roughriders, a team that had no playoff appearances in the past 11 years. While the Saskatchewan Roughriders finished in 4th place in the CFL West Division with a 5-12-1 record in his first season at the helm of the Western Riders in 1987, the following year, he led the Riders to an 11–7 record and a playoff berth. He won the Annis Stukus Trophy as the league's coach of the year. In 1989, the Roughriders finished 9–9 and won the 77th Grey Cup, their first since 1966. After a 1–6 start in 1991, he was fired and replaced by Don Matthews. He had a 35–43–1 overall record in Saskatchewan.
That same season, he was hired to replace David Beckman as head coach of the 0–8 Hamilton Tiger-Cats. He made the postseason two of the four years he was with the team and finished with a 24–40 record.
In 1995, Jim Foster hired Gregory to build an Arena Football Leagueexpansion team in Des Moines, Iowa. Gregory coached the Iowa Barnstormers to five division titles in six seasons and led the team to two ArenaBowls. Quarterbacks Kurt Warner and Aaron Garcia are considered two of the greatest AFL players ever. Gregory was named AFL Coach of the Year in 1995 and 1996. The Barnstormers relocated to New Yorkin 2001, becoming the New York Dragons; and Gregory left the team in 2003. Gregory later joined the Carolina Cobras as offensive coordinator under Ed Khayat; after a 2–4 start to the 2004 season, Khayat was fired and Gregory took over. In his first game as Carolina's interim head coach, playing the defending ArenaBowl champion Tampa Bay Storm, the Cobras scored 24 unanswered points in the third quarter to win 54–43; it was the team's first home win since 2002. However, the Cobras suffered a losing streak that dropped them to 3–7, leading to Gregory's dismissal with six games left in the season. In 2005, Gregory came out of retirement to coach the Arkansas Twisters. He went 5–7 in his first season and 10–6 in the 2006 season, losing the National Conference Championship to the Spokane Shock. In 2007, the Twisters improved to a 12–4 record, a franchise best, but lost to the Bossier–Shreveport Battle Wings in the first round of the playoffs. In 2007, it was announced that Gregory would return to Iowa to coach the new expansion Iowa Barnstormers. On May 17, 2011, Gregory resigned from his position with the Barnstormers. In 2012, Gregory was the offensive coordinator for the Tampa Bay Storm. It is his first position where he has not been a team head coach for more than two decades. He was the commissioner of the National Arena League during its first season in 2017.
