If you haven't seen this, check out Bob Keller's Impro-Visor, a software improviser that's surprisingly good! He was one of my CS profs in college but also had a side passion for jazz. Dude could play well too.
After a look a the key (2 sharps) and the chords, if the key is the same that on the part with the melody, the chords are in Eb.
First to pratice it yourself, you will need a play along that play the chords when you pratice voer it, there are many app that do that :
iRealPro http://irealpro.com/
ChordPulse http://www.chordpulse.com/info.html
To chorus on the chords :
1- Play the tonic/bass of the chord for the whole duration of the chord, to feel the progression
2- Play the third of the chod for the whole duration of the chord
3- pratice until you are able to play on the whole 12 mesures : 1-3-5-7-1'-7-5-3 in 8th (where 1 is the tonic of the chords of the current mesure, 3 is the third... for example D-F#-A-C-D'-C-A-F# // G-B-D-F-G'-F-D-B)
4- hide the name of the chords and chorus on it multiple time. If you do some stuff that sound good try to remember it
Never tried them, but there are a couple of open source automatic accompaniment programs:
Another option would be to download MIDI arrangements of songs from one of the many websites.
Yes, iReal is the one with best sounds and coaching.
As for theoretical understanding of harmony there is something interesting called "Impro-visor". The built in sounds are so-la-la but it has some unique features as an on-the-fly harmonic analysis. It is java based and free
You might want to check out:
SightReadingFactory.com. It actually generates some pretty cool stuff and will play it for you at a specified tempo. Paid subscription. I think it's well worth it!
Impro-visor. It's a very useful piece of software. A lot of depth and functionality. Can generate parts, based upon a chord progression you specify. Available without cost at SourceForge (follow the links).
Band-in-a-Box. I've been using it for years and think it does a great job. You turn it on and it'll generate a lead for you against any progression that you want. Similar to Impro-visor with a lot more capability. The downside is that the fees can be pretty hefty! I'm a satisfied customer.
/kengon
There's also improvisor which seems like a really ambitious project but comes with a lot of standards in its "imaginary book" and does support direct chord entry. Also, it's cross-platform and if you can set up the MIDI out you can have it trigger sounds from your favorite DAW if you prefer. I should add that it's gratis and free software.