In my quest to learn composing simple game music I thought I should study some old Mario songs because the simplicity of never having more than 3 notes at the same time. The Starman Theme starts with C, D and F. I thought this was a bit strange because these does not make up triad with notes a third apart.

To me it would make more sense if it used B, D and F because then they would be a chord consisting of a root, a third and a fifth. When I think about it I realize B, D and F would make up a B diminished chord so that would probably not sound very good but I don't understand how to think when using notes that are not part of a traditional chord. Why did they do it the way they did? Is there any "rules" to follow?

That's the rule of "Does it sound cool?" As any rule in music composition, disobey it when you feel like it, but at least be aware you do. ^^;

It's a D minor 7 chord, without the 5. That's why the D is in the bass line. The full chord would add an A, but that can get crowded and often the 5 doesn't add a whole lot to the tonality. And guess what the next note to appear in the bass is?

You need to familiarize yourself with all of the seven chords, as well as inversions. That covers your core 'traditional' chords. It may also be helpful to look at suspended chords.

The progression seems to be Dm7 (D minor with the dominant 7th), Cmaj7 (a C major chord with the major 7th). These are known as extended chords, so they are root - third - fifth chords with an added 7th. A D minor chord is D, F, and A, and the dominant 7th is a C. A C major chord is C, E, and G, and the major 7th is a B.
So the root of the first chord is actually a D, not a C. 7th chords give you a different character than standard triads (three note chords).
The dominant 7th would be one whole step down from the root note of the chord. In the case of D, the dominant 7th is C. A dominant 7th chord is simply labeled with a "7" after it. Dm7 = D minor with a dominant 7th added in.

The major 7th of a chord would be one half - step down from the root. So for the second chord, which is a C major, the major 7th would be a B.
A major 7th chord is labeled with a "maj7" after it. For example, Cmaj = C chord with the addition of the major 7 (B). The "maj" part of the nomenclature does not indicate whether the chord itself is major or minor, only that the 7 is a major 7th and not a dominant 7th. It is implied that the chord itself is major because the minor is not indicated.

There are always rules for this stuff, but use your ears and play around with extended chords and you'll be fine. Tweak it until it sounds right, and over time you'll notice things that work and things that don't work. This will speed up your composition process. Just keep working at it, and trust your ears.

Oh also, the reason this works is that the song is in the key of C and all of the notes used are in the C major scale.

I was not expecting any notes to be missing because then you can just use a thirteenth chord and be able to use all the notes in the whole scale. :p But it makes sense that it's a 7th chord now when you say it. The first two bars only contains the notes D, F, A and C. The next two bars are the same except that the notes has been moved down one step in the scale, and then it repeats, so that's why the progression goes from a D chord to a C chord.

This must mean that the chord progression for the whole piece is ii I ii I ii I ii. I'm not very good with chord progressions yet but don't chord progressions usually contain IV and V, or is that only important in "real" music?

This must mean that the chord progression for the whole piece is ii I ii I ii I ii. I'm not very good with chord progressions yet but don't chord progressions usually contain IV and V, or is that only important in "real" music?

It's an extremely common resolution of a chord progression, especially in say, pop music (of most varieties). But, it's by no means a rule. Perhaps read up on things like the "circle of fifths" and diatonic function. Where a note lies in relation to the tonic creates different tensions, and they can be resolved (or not) in different ways. IV V being a very common way.

I think game music differs a bit sometimes, in that often you don't want to resolve things, and just keep the music sounding rather intense and driven. A complete resolution in the middle of a level might even seem rather off-putting with certain progressions.

And it makes sense, listening to the song, that it doesn't really ever resolve to anything at all. It's not really even a song, so much as a simple looped phrase. A resolving version might go ii V I instead.

I was not expecting any notes to be missing because then you can just use a thirteenth chord and be able to use all the notes in the whole scale.

9, 11, and 13 chords are totally normal in jazz progressions.

In my quest to learn composing simple game music I thought I should study some old Mario songs because the simplicity of never having more than 3 notes at the same time

When looking at old chip tune music, you really should consider any technological limitations at that time. The NES could stream four channels and one was used for both music and SFX (which is why some of the music would drop out if you were getting a lot of coins at one time). So that really left three channels of steady music streaming. The composers at this time knew all of the limitations and wrote music to accomodate those limits.