Ok, I got it to work! The second time I took the battery out, I left it out for about 5-10 minutes before putting it back in. And for whatever reason, it started back up again. Battery shows a 99% charge - seems strange to me.
Oh, and it's probably clear to those of you in the know, that I don't know what I am doing, but to clarify for others like me:
Holding down c only helps if you have a CD/DVD in.
Pressing "option" leads to the computer showing all boot options.
Holding cmd+s will give you a command line allowing you to use fsck.
But none of this matters if the computer isn't bonging.