[The below is based on my experience as a windows programmer]
Most of your apps wouldn't have to be rewritten. Most of the software is probably already multi-threaded. If it weren't, the UIs would freeze everytime it tried to do some intensive background processing. I have not written an Android app yet, so I'm not sure of all the things you need to take into account, but I assume there is a decent amount of background processing for most apps.
All processing threads get queued by the kernel and they take their turns using the CPU. The only difference when there are multiple cores is that the kernel can give work to more than one core at a time. The software is pretty much stupid about how many cores are on the machine. The software just tells the kernel it wants to do these 3, 4, 5, 20 things concurrently. The kernel does the hard work of figuring out how to divide that work up amongst the 1, 2, 4, 8 (etc.) cores.
(Even if you have 1 core, the kernel gives each process a little bit of processing time round-robin style. They each take turns doing a little bit at a time, but do it so fast, that everything is seamless).