Watch the Complementing Melody online guitar lesson by Larry Carlton from 335 Improv
A good rhythm part supports the melody without getting in the way. If you start the progression here with a Gmaj7 voicing that has the maj7 (F#) on top, watch out - it's going to clash with the melody, which moves from the maj7 (F#) to the tonic (G). Instead, stick that maj7 on an inside voice.
The accompaniment should have a great pulse and never be too static. For this tune, I like a part that matches the rhythm of the melody. The top of the melody is the song's hook, and it has a motif that works nicely in a backing part.
With that motif in mind, check out the notation where I've included a few nice voicing choices to start with. Try playing the rhythmic motif while using those voices. Once you're comfortable with the ones I've provided, mix in your own voicings and also try your own variations on the rhythms.