There are two basic ideas of making your applications smaller:

1.) Removing files directly from APK - This method is usually enough for graphically intensive applications (weather widgets, ...)

Make a backup copy of the APK
Rename .APK to .ZIP if you need to
Open the file with the ZIP utility (7-Zip, WinRAR, Total Commander)
Get familiar with the folders inside the APK
Most files will reside in /res/ subfolders. There are usually PNG and XML files.
The ones that might be useless are usually in "drawable-hdpi" and "drawable-ldpi" folders. Because Spica has a 320x480 screen (referred to as "mdpi" or medium density), but other phones have lower or (usually) higher densities, you can often delete the files intended for other screens without corrupting the application.
If there is a folder such as "drawable-mdpi" or "drawable", the files for Spica are probably there...
...unless the number of files in "drawable-hdpi" folder is larger than the number of files in "drawable(-mdpi)". This means the application was mainly developed for larger screens and the main files might be in -hdpi, and then either replaced by -mdpi versions or scaled down from -hdpi images.
You usually cannot replace PNG files directly (for example with an optimized image). This is because every file has a special signature (in /META-INF/ folder), and any modification of the file will change it's signature, and the APK won't install. If you wish to replace files, you have to use the second method.
Install the modified APK and test it.



2.) Decoding and rebuilding the APK using apktool - This method gives best results, includes the first method, but there is also more chance something will go wrong (application FC).

Make a backup copy of the .APK
You must have Java installed, as well as apktool (or APK manager)
Decode you APK (apktool d someapp.apk)
The folder "someapp" will be created, containing the files from the APK as well as many others (mostly XMLs)
You can now modify the files inside the /res/ subfolders.
The PNG files usually cannot be deleted. They are referenced by .XML files, and if they are missing, the apktool cannot build the APK and will quit.
You can often delete some of the XML files directly. Usually those files are in "raw-*", "layout-*" subfolders and contain localizes strings (other languages). They may be successfully removed because the main strings (english) are in the "layout" folder. Do not remove the "layout-land" and "layout-port" XMLs because those are needed for landscape/portrait orientation of the application.
Build the APK (apktool b someapp someapp.apk). You should probably try this after every (major) change. If the build doesn't succeed retrace your modifications until it does. *
New finding: some APK files contain folders other than "/res" (and "/META-INF"). These folders have to be copied from the original APK into the new APK at this point, before testsigning the APK.
Test sign it (java -classpath testsign.jar testsign someapp.apk) *
ZIP align it (zipalign 4 someapp-temp.apk someapp.apk) *
NOW you can delete the unwanted files (first method)
If you have an original version of the application installed, remove it first. The modified version will not install because it has a different certificate (testsigned).
Install the modified APK and test it.

* These steps can be automated by using "build.bat" from this script (see readme.txt inside the ZIP)


Feel free to experiment, there's not much you can screw up, apart from the application not installing or running. But you made a backup, right?
The tutorial will be updated based on addition questions/remarks below.