gwt-user.jar is the library you work with, regardless of whether you are developing client or server code. It contains everything, user interface widgets, utility classes for the client side, and utility classes for the server side.
gwt-servlet.jar is used at runtime. I'm not talking about development mode, but about running your web application on some kind of web server (Apache, IIS ...). Gwt-servlet.jar contains the classes that a web server needs to run GWT materials on the server side.
So, the Base64Utils class is in both JAR files. However, it is not available for development on the client side.
If you need something that works on both sides, check this out:
http://www.source-code.biz/base64coder/java/
source share