You got it (take it you have Photoshop 6 or 7):
1) I started out by making a couple simple shapes that could be easily duplicated to create the diamond pattern, and made them in opposite rows, such as:
\ \ \ \ \ \ \
/ / / / / / /
Obviously I started out with one oval shape with tightened ends on a new path layer. When I felt as though I had the proper spacing and structure, I duplicated it for one layer, and duplicated+flip horizontal (or mirror) for another row. Then I had two rows that I could easily duplicate as a pattern.
When creating the paths, you may use the active bar above to highlight all shapes and space them out accordingly (this is easiest in Illustrator).
To paraphrase: Build one oval structure to you liking using a vector path, and duplicate it to mirror the pattern you choose. This is your basic starting point, the structure.
2) Make two layers: one is a solid background, the second is your paths filled in with whatever color you'd like for the diamonds. You now can start to apply textures and techniques.
3) I cheated and used a plugin here -- Flaming Pears Super Blade Pro (for the texture), but we'll get into that. For the dimond layer, I applied a beveled style to it (again by double-clicking). This creates depth that can be easily manipulated. You 'can create layers' to the effect to make it much easier for you to paint with it. Later on, I duplicated that shadow bevel and darkened it in some spots and feathered it in others.
4) I used some distorted stock photography, blurred it, and used it in the background. I have not changed all the colors yet. I then applied the Super Blade Pro filters to it that gave it looks of rust, weather, wear, rain... doing it the old way would have been hours of painting. You may download this filter and purchase it at http://www.flamingpear.com
5) After tweaking some of the edges and painting here and there, I applied a Hue & Saturation to the image (select colorize in the bottom right box when the menu pops up) to make it sort-of monotone drab color.
6) Finally, I went back over the color and sprayed in some rus looks and stuff that it lacked a little.
That was a brief explanation to get you started a little bit -- I hope that I wasn't too short, and if you have further questions, please ask
I know a simpler technique would be to make that pattern as stated in number 1, and place it in the patter overlay folder or make it a paint brush.