I'm starting this community wiki to get all the interpreted languages that can be embedded, but let's begin:
Now if I missed some language, please post and remember to put the link. Thanks.
Actually Ruby is said to be possible on iPhone, Blackberry, Windows Mobile and Symbian/Android ( soon ) by Rhodes
You can also get python for PSP, if that's the sort of thing you're looking for.
Java might be the most ported, it's on a whole bunch of mobile platforms (but that's way on the outer edge of interpreted), I have heard that Python is ported to more platforms than Java, but I can't verify that.
List of python on other platforms
Python for PSP seems to no longer exist. Their website is down.