"The governor shall communicate by message to each session of the legislature information touching the state and the country."
Generally, an inaugural address is given the first year in office and a state-of-the-state address every year thereafter. The governor usually also gives a budget message at the beginning of each legislative session and sometimes special budget messages.
The state-of-the-state address has not always been called that. According to research done by the Legislative Reference Library, Governor Harold LeVander's 1969 message to the legislature was the first one to be titled "State of the State."
Visit the Minnesota Legislative Reference Library's Gubernatorial Addresses to the Minnesota Legislature for more information and for text and video for many annual and special addresses.