I think jazz musicians come up with their chord substitutions mostly by ear. I don't mean because they're uneducated--jazz players are probably the second most likely musician to have a solid grasp on theory, after classical musicians--but just because it's the nature of the style.
That said, there are some common strategies that have developed over the years.
The basic principle of chord substitutions, in jazz and otherwise, is that you replace a chord with another that shares some of the same notes. Since Western harmony is based on thirds, an easy way to do that is to start with a chord that's a third higher or lower. So, if you have a C7 chord, being C-E-G-Bb, you might try substituting a half- or fully-diminished E seventh chord, E-G-Bb-D (or E-G-Bb-Db). The "E-G-Bb" part remains common between them. Alternatively, you might keep only two of the notes: say the C and E, in which case you might try chords like Amin7, A#dim7, or Fmaj7. These may be less likely to work, since they share fewer notes with the original, but they might be worth experimenting with.
A big part of whether a chord substitution will sound appropriate or not has to do with which notes you preserve versus those you substitute. Mostly this boils down to functionality and "structural necessity". That is, the more necessary a note is to a chord's identity or function, the more likely it is that a substitution chord will feel better if it has that note.
Deceptive cadence example. According to basic music theory, as you probably know, the vi chord can be used in place of a I chord after a dominant harmony, which creates a "deceptive cadence". Part of the reason this works is because the vi chord shares two notes with the I chord: the first and third of the I chord, which are the two most important notes for the I chord's identity. (For example, C and E in the key of C.) You can sort of make a deceptive resolution to the iii chord instead of the vi chord, since iii also has two notes in common with I (that is, E and G in the key of C), but it doesn't work as well, because the tonic is integral to the I chord's identity, and because the leading tone of the dominant feels like it should resolve to the tonic as well.
Tritone substitution example. The most important part of a dominant harmony is usually the tritone formed between the leading tone and the 4th scale degree. Thus, you can stick any other chord with that tritone in it wherever you'd normally have a V7 chord, more or less. So, in the key of C, the leading tone and 4th are B and F, which we see in the V7 chord as G-B-D-F. Another common dominant harmony is one that's up a third from that, which is to say, a diminished B chord: either B-D-F-A or B-D-F-Ab. You see that in both classical music and jazz a fair amount. In jazz, there is also the idiomatic "tritone substitution", where you get a dominant 7th a tritone away from what you'd normally use: so, instead of a G7, you'd use a C#7 (or Db7 depending on how you want to spell it). This is basically the same thing as using a dominant 7th chord one half step above where it will resolve--e.g., instead of Dmin7, G7, C, you might have Dmin7, Db7, C.
To see why this works, spell out Db7: it is Db, F, Ab, Cb. Now, Cb is enharmonically equivalent to B, which means that Db7 contains the same B and F that, as I said earlier, are what's most important for a dominant function in C.
(Another potential reason this might work is that a dominant 7th resolving down one half-step also has the same notes as a
German sixth resolving from a pre-dominant to a dominant, but let's not get into that.)
... Ehrm, let me know if this doesn't make any sense, I'm kind of spacey feeling as I write this.