This is a very broad question, and each individual subquestion is very broad by itself, but I'll try to point you in the right direction.
You should grab a copy of either Mark Levine's "The Jazz Theory Book" or Robert Rawlins' "Jazzology". In my experience, those are the most recommended general jazz theory books. Check reviews in Amazon and similar sites to see which one suits you best.
How can I put melodies together in a way that sounds good?
That's a very subjective question, and only experience will tell you what works best for your taste. Jazz theory can give you general recommendations on when, how, and why use specific scales, but in the end it is up to you to grab all that information and use what you want and like.
The specifics would require a question on its own, and even there it might be still a very broad question. It is a very large subject.
What are some common scales that are used?
Depends on the style and context. The major scale and the 6 modes derived from it, pentatonic (minor and major), blues (minor and major), diminished (whole-half and half-whole), augmented, the melodic minor scale and some modes derived from it (including altered and lydian b7), and bebop (dominant, minor, and major) are all very common.
What are some exercises that would help?
There are many, and depends on what exactly you want to practice. For scales you should be doing normal runs for speed, but also stuff like "four directions" and "going up one mode, down the next, etc" as in C D E F G A B C, D C B A G F E D, E F G A B C D E, etc (the details of this can be found in Mark Levine's book, in the "how to practice scales" section.
There are countless more. Ear training is important too.
Are there any good licks that I should know before I start?
Transcribing is a good way to expand your jazz vocabulary. Again, good is subjective. Search for licks that you like and transcribe them. Play them in different keys, expand on them.
If you are into bebop and hardbop, John Coltrane's album Giant Steps has countless exceptional licks. The track "Mr PC" is a good starting point, since the harmony is a simple minor blues. If you are more into cool and modal jazz, Miles Davis' Kind of Blue is also filled with out-of-this-world licks. Those two are probably the most well known jazz albums and both have John Coltrane in the sax, so you will most likely find something that interests you.
Are there any techniques specific to jazz I should know?
That's way too broad a question, and jazz is already too board of a concept. You'll find them as you progress.
You need to start a program. Grab one of the recommended books above, and/or get a teacher. You can find quality teachers online if you can't find one in your area, Berklee has good online improvisation programs. That way you'll answer those questions in detail as they arrive in your program.
There is no shortcut.
A good place to start
Regardless of what path you take, a good starting place is improvising over a common 12 bar blues.
Learn one minor blues scale, whichever you want, and play it over a blues in that key. If you learned C minor blues, you can play it over a common 12 bar blues in C or a common 12 bar minor blues in C minor, through all the song.
When you feel like you can handle that, learn the other minor blues scales that correspond to the chord changes of the blues that you are learning. For example, using the last example of a blues in C, the other chords are F7 and G7, so learn F minor blues and G minor blues scales, and play them with the chord changes.
That's something you can do right now. As you progress you will learn more scales and more stuff you can do over a blues and other harmonies.