What I did: (2001 Montero)

1) I took off all the plastic moulding pieces (oh-sh*t handles, etc..)
2) Then sprayed on a bunch of carpet cleaner & rubbed it in & off with an old shirt.
3) Rented a carpet cleaner at Vons for $32.50 (including upholstery attachment) and did a finally cleaning.

It actually came out very nice.

It can't be any worse than how my headliner was! It had numerous I don't know what stains and crap on it (actually the whole interior was trashed. My X-B*tch never cleaned the car the whole three years the court allowed here to keep it while the divorce was in process.