I'm the developer of an extremely portable mobile game that runs on everything from PCs, to TVs, to even the Black & White Amazon Kindle (Smiles HD - http://smileshd.com - More devices and platforms than you see there).
The best way I've found to support any device is to pick a base resolution, then scale up (or down) to the current screen. If you want to cheat, you can fit to the new screen resolution, but ideally you should keep the same aspect ratio. Fitting a game made for a 4:3 display looks hideous on a 16:9, but fitting a 16:9 on to a 16:10, nobody might notice. You'll note I refer to screens by aspect ratio and not the dimensions, which is especially helpful way to think in this era of totally random LCD sizes.
To make artwork that suits any screen while maintaining the aspect ratio, create backgrounds that are larger than most typical screens will ever see. This is similar to the concept title-safe areas with Television.
Generated backgrounds work really great for this. Tiled patterns, checkerboards, fractal shapes, etc. You just need generate a little bit more to fit a new screen.
Also, creating static images larger than what your typical user will see. Wider than widescreen (16:9), and squarer than standard def (4:3). Again back to title-safe areas, fit your important information in to a safe area, scale up a bit so your safe area touches one of the edges of your screen, and leave some run-off for devices that are just a little bigger.
A variation I'm working with today is creating "title safe" 3D objects. Since they're 3D, composed entirely of vertices, making them larger than the screen takes up practically no more memory than if they were to fit. Just as the density of pixels goes up, you may want some higher detail textures available. If not, oh well, it's a little blurry.
User interfaces, I like to fit the main UI within a perfect square in the middle of the screen. The corners and the middle edges also make really good places to put things; You should calculate their coordinates as such (relative the corner or the middle edges).
If you really want to get fancy, you can support both Tall and Wide orientations. Some devices do report their screen resolutions as taller than wide (iPhone for example), so you may have to do something for those devices anyways, even if it's simply rotating all of your coordinates.
A User Interface that adapts to both tall and wide screens can be a pretty impressive sight.
On the plus side, design wise, you only really need to consider Tall and Wide, instead of Portrait+Reverse Portrait+Landscape+Reverse Landscape. When you pick the positions of things on the screen, consider having a more appropriate alternative position for the other orientation.
Do I need to keep big versions of all images and scale down depending on the resolution (doesn't that waste space)?
Well you can either "waste space" and support a wider variety of devices with a single build, or "waste your time" and have to make MANY builds and resize artwork for many devices.
Best case, you should create your artwork at higher resolution than the final size would be on a 1080p Television (1920x1080). 2048x2048 should be a common size in your source artwork. Either that, or consider using Vector artwork tools like Flash and Adobe Illustrator.
I'd strongly recommend creating an automated process for resizing your artwork. Most mobile devices today, tablets included, do not exceed resolutions greater than 720p (1280x720)... at least, not by much. Come next year though, we just don't know if that will be true anymore (iPad 3?).
Either way, for best performance, you should get used to the idea of source artwork and source assets. You can then perform a process that optimizes the data for whatever device(s) you are targeting.
Do bitmap fonts scale well or do I need to use something else?
They scale well if you're using a good filtering. If you're making your 2D game with 3D hardware (OpenGL ES), then I must strongly recommend that you use Linear Filtering combined with MipMapping (i.e. a set of scaled down images). You can get perceptively perfect results with this, and it's often faster to use mipmaps than not to.
Anyways, I hope that helps. Best of luck with your project.