Originally Posted by: bbreon75It's easy finding the melody and playing it but I don't know how to find the chords to play for the rhythm. Any tips?[/quote]
Ask the people playing the songs, "What are the chords in this song?"

Then write them down and look at them while you practice them along with the recording on your own or with the band.

Originally Posted by: bbreon75
1. Is there a way to find out what chords will work with the song just by knowing what notes the melody follows?[/quote]
Yes, it's a matter of knowing harmonic possibilities.

If we build a chord (a triadic sequence) on every note of the major scale using only notes of the scale in the same pattern. I informally call this the "Leapfrog Principle" because you start on a note (C) and "leap over" the next note (D) to use the following note in building the chord (E). Leap again over the (F) and use the (G). Hence, the first chord is built of the notes C-E-G. This is the basic principle known as Triadic Harmony.

C - E - G = 1st scale degree - 3rd scale degree - 5th scale degree = the "one chord" of the C major scale. So, the chord built on the first scale degree of the C major scale is a C major chord.

The distance (the interval) between the notes of the chord gives us the formula for all major chords: 1st note of chord, 4 half steps (or 2 whole steps), 3rd note of chord, 3 half steps (or 1 and a half steps), 5th note of chord.

The formula for minor chords is: 1st note of chord, 3 half steps (or 1 and a half steps), 3rd note of chord, 4 half steps (or 2 whole steps), 5th note of chord.

The formula for diminished chords is: 1st note of chord, 3 half steps (or 1 and a half steps), 3rd note of chord, 3 half steps (or 1 and a half steps), 5th note of chord.

Now we now all three types of triad chords we will encounter in major scale harmony. So we build a chord on every note of the C major scale. Here is the list of all the chords:

C-E-G = 1-3-5 (the "1 chord") C major chord
D-F-A = 2-4-6 (the "2 chord") D minor chord
E-G-B = 3-5-7 (the "3 chord") E minor chord
F-A-C = 4-6-1 (the "4 chord") F major chord
G-B-D = 5-7-2 (the "5 chord") G major chord
A-C-E = 6-1-3 (the "6 chord") A minor chord
B-D-F = 7-2-4 (the "7 chord") B diminished chord

Notice that every chord has 3 notes - its own 1st, 3rd & 5th unto itself. This is a crucial point: every note in the major scale has 2 separate and simultaneous functions.

1. Its position in the scale.
2. Its position in any given chord.

E|-------------------1--3------|
B|----------1--3--5--3--5------|
G|-0--2--4--2--4--5--4--5------|
D|-2--3--5--3--5--7------------|
A|-3--5--7---------------------|
E|-----------------------------|
C--D--E--F--G--A--B--C

In music theory we use Roman Numerals to number the chords - usually, upper case for Major chords, lower case for Minor (and diminished). We also refer to the chords by these names which relate to their function in a chord progression (written to match the C major scale which we harmonized above):

I - "1 chord" is Tonic (or Root) - C major (I)
ii -"2 chord" is Sub-Dominant - D minor (ii)
iii - "3 chord" is Intermediate (or Mediant) - E minor (iii)
IV - "4 chord" is Sub-Dominant - F major (IV)
V - "5 chord" is Dominant - G major (V)
vi - "6 chord" is Intermediate (or Sub-Mediant) - A minor (vi)
vii dim - "7 chord" is Dominant - B diminished (vii dim)

Therefore, a Tonic chord is a chord built on the 1st note of the scale.
Therefore, a Dominant chord is a chord built on the 5th note of a scale.

So if the melody note of a song is an E it could belong to the C major (the I chord) or the E minor (the iii chord) or the A minor (the vi chord). But, it could also belong to the F major chord and be the major 7th (a IV maj7 chord).

I am currently working on a brief overview of music theory containing info on diatonic and functional harmony and will post it soon. For now, look here:
http://www.guitartricks.com/tutorial.php?input=166
http://www.guitartricks.com/tutorial.php?input=167
http://www.guitartricks.com/lesson.php?input=10978

Learning and understanding this info will certainly help in the future. But simply asking for the chords will be a lot more straight forward and more efficient. That way you can have the chords and see how and why they work. Simply knowing all the harmonic possibilities is not a guarantee you will be able to pick the same chords that any given musician will also pick.
[QUOTE=bbreon75]
2. Is the I-IV-V the "rule" when I find out which key I'm in or could there be other notes available (which would make my plight more difficult)?

Although that is a very common progression it is by no means the only one. For the most common exception consider that many songs use I-ii-V. Also, some songs don't even start on the root, and use ii-V-I.
[QUOTE=bbreon75]
3. Do you have a "golden nugget" piece of advice that will lead in on the quickest path to being able to play with a band and play good (lead & rhythm)?