Well first get a plan of what you want it to do. Sounds like you just want to use it for music.
Your best and sometimes cheapest way to go about it is to find a good all in one motherboard. That way you will not need any additional cards and will minimize the size of the case. You can find some on eBay for a good price. Look for onboard Audio (SB compatible), video, and LAN (if needed).
Power Supply: $15-$40
You have to think about if you want to be able to take the computer out of the car and use it elsewhere. In that case you will need a regular power supply (w/ inverter). If you do not plan on taking it out of the car you can go with a DC-DC power supply (I don't know much about these power supplies, but you can search this forum).
I found that most ATX power supplies are kinda tall and will make the case tall also, so if you go this way you could forget the all in one MB and use sound, video and LAN cards. You can find many cheap used ones and it could end up costing less.
75Mhz is all you need to decode MP3s. This is if you will be using DOS. If you are using Windows I would suggest 133Mhz. Any more than this will depend on what you will be running, and if in the future you want to use other things as in GPS or video.
I personally regard RAM as a higher priority than the processor. I would suggests 64MB as a minimum. With RAM prices today I would go with as much as I could afford. I see people with 600-800Mhz processors in there computer but with only 64 MBs of RAM and I just have to laugh. But that is a whole nother story!
Hard Drive: $40-$300
Take the total space of MP3s you have and add 2 Gigs for OS space, and extra storage room. You should mount the drive in a vertical position. This will help prevent damage to the disk from bumps and vibration. There are some manufacturers that claim a high G-force rating on their drives. I have heard that Maxtor is one of the best.
If you are going for just music I would suggest a 2x40 or 4x40 character LCD. If you would like visualizations or plan on using Windows, I suggest a 5" or larger LCD. The price of these can get pretty high, especially the VGA LCDs. You can use the 2x40 and 4x40 in Windows with no problem, for just music. That would be your best bet!
This is where it gets personal! I have seen many types of cases using many types of materials. You can make your case out of plastic, wood, plexiglas, acrylic, and even metal (if everything is insulated very well). It is up to you. You can go through the websites on MP3Car.com and get ideas. You may think about using a standard PC case too.
How do you want to control the computer? Alot of people use just number pads. You can also use remote controls, joysticks, touchscreens, and mouse pointers. This is up to you!
This is a VERY general checklist, and the prices are what you COULD (or should) be paying (US dollars). You should try to use any hardware you already have to keep the price down. As far as walkthroughs about building a car computer, this is a personal thing. It is kinda asking how to build a house. I have never seen a car computer built the same. If you let me know what you want it to do and what your budget is, I would have no problem giving a more direct description of what you should be looking for and doing to build your car computer. My suggestion is to look at what other people have done, and most of all ask questions! This message board is a holy grail to people like you and me, use it!