I guess to answer your question more accurately, perhaps more encouragingly, it might be appropriate to ask a few questions. Specifically, do you want your creation to have all of the same features as a car stereo? Because playing CDs and digital media is going to be very tricky. I didn't say impossible. That's not really a word we should even use anymore in my opinion.
If you want to make a car stereo using an Arduino, go ahead and do it, but pace yourself because it's going to take a very long time to get everything right. Perhaps the best approach would be to break this up into several smaller projects and work on each of those to a completed prototype. You will learn a whole wealth of new things and will improve your skills considerably. Some of the information you will need is going to be difficult to find, some other things you will just have to figure out on your own. The internet is your best resource for a big project like this.
I'll give you the first piece, this is something I have been wanting to build for a while also, but I have several other projects to put on my work bench first. I've been trying to get through two or three small projects a week, now that I have enough spare parts in my home lab to keep me building.
This project is going to be fun as long as you don't get discouraged. It's an Arduino controlled FM receiver.
Linked externally from hackster.io: Arduino tea5767 fm radio receiver.
This uses a TEA5767 FM receiver. You can get these as cheap as $4.50 USD and a Nokia5110 LCD display, but you can certainly use different displays if you want. Maybe a 16x2 would be more suited to the car stereo form factor. Anyway, I found the Nokia display for $3.72 on Amazon. All of the parts can be gotten pretty easily and cheaply online, a little more if you want faster shipping of course.
This is where I would start. Once you get that working, you can start the feature creep. Add programmable station buttons, maybe a seek function. Add in a good stereo audio amplifier. You may find that you need some signal filtration to block unwanted RF interference but that's just a guess.
There are other tutorials around for playing MP3s using Arduino, watch out for the ones that require you to use proprietary hardware or shields. They will probably work, but aren't going to fit into your finished design so don't get comfortable with them. Connecting the Arduino to a vehicle's power source is also going to require at the very least, some good power regulation, so you may find at some point that you're designing a DC/DC power supply to drive the stereo and resulting audio amplifier.
Is it possible? Heck yeah it is. Start building!