The JavaScript Engine is only included in the Sun/Oracle JDK. If you use some other Java implementation like IBM J9 or Oracle JRockit (quite likely on a server), or if you don't use the Sun/Oracle JDK but the Sun/Oracle JRE (even more likely on a server), then you don't get the JavaScript engine.
You need to use Sun's full JDK.
Note also that the JavaScript engine shipped with JDK6 is not Rhino, it's a stripped-down lobotomized version of a several year old obsolote release of Rhino. In particular, it is missing the compiler, which means that performance will probably suck.
Also note that the API is not necessarily compatible between Rhino and the JDK6 JavaScript engine, even if you manage to find that obsolete release of Rhino that it is based on. So, if you want to use Rhino in deployment, you'd better use it in development, too.
And last but not least: just because you make some entry in your Eclipse project file, doesn't mean that your server's classpath is going to magically change. You need to make sure that all your classpaths are properly set up. I don't have any eperience with FreeBSD, but I'm pretty sure that the package management system (FreeBSD ports in this case) is going to at least partially take care of that after a port install rhino
.