Depending what you want to do, I'd wait until at least April. Then you'd be past most of the snow. There will still be snow in the higher elevations through May and even into June. Everything unpaved is muddy in late spring during "break up". Mid-May to Mid-June is usually cold and rainy.
For the absolute best vacation to Montana, for most people and most adventures, is July, August, and September.
It's always cold at night, even in July, so plan for it. As soon as the sun gets low in the evening, the temperature drops fast. It can by 95 degrees at 3:00 in the afternoon, and drop below 50 before midnight.