Scales are an important and necessary part, but I agree with ZenoArrow - developing aural skills is the key. It opens up so many possibilities.
I haven't fully mastered those skills yet (still working on them), but learning just a little is like suddenly having a map while trying to find your way around a city. Before, you stumble around, stopping to ask for directions and taking wrong turns. After, you can plan what you want to do much more easily.
The key to musical improv (as opposed to experimental improv, which has its place) is meaning to play what you play, and you can only truly be free to do that when you know what the notes sound like before you play them.
For example, let's say you were learning guitar, a good exercise would be to look at a random note on the fretboard (for example, the 10th fret on the G string in standard tuning) and sing the note, then play the note and see how close you were. When you can do that reliably, that's a big step forward towards mastery IMO.
However, I would recommend starting with ear training for relative pitch rather than absolute pitch (which is what the exercise above is for). For that, you play a note, then sing a note a certain interval away from it (e.g. a minor third) then play the note which is a minor third away from the first note. I believe this is a great exercise to start with.