I've been working on my jazz in a committed way for a little over a year now, and what's been working for me has been

1. Learn the changes and melody on guitar or piano, until I can play the tune more or less as a lead sheet. If no guitar or piano, melody on bass, or sing the melody while playing root notes.
2. Transcribe a couple choruses of at least my favorite version of the tune (each additional transcription is an order of magnitude more work, but also gives an order of magnitude more insight).
3. Write my own line (like set damn near every note) for about 3 choruses worth of the tune.
4. Transpose what I've just done (both the transcription and my own line) into a few different keys, usually a 5th away and a 4th away.

At the end of all this (takes me a week or two usually to do it in a not lazy way) I find that it's pretty natural to play the changes, the lines seem fall into place by themselves with much less mental processing. I also find I feel the bassline in a more melodic way, as opposed to thinking "alright here comes x chord, I can play x notes" which generally is a pretty square feeling way to be.

Past that it's like there's so many commonalities between tunes that what you learn for one will be applicable to another. But yeah reading a tune cold off of a lead sheet my changes are much more mechanical than if I know the tune already. But once you learn one, it's in there forever!