I have the Android SDK installed on both a Linux machine using open SuSE 12.1. I've used both machines to successfully build Android apps many times and sign them both with a debug key for testing and a release key from my own keystore, so it should be somewhere on each machine.
Using the command
find -name jarsigner
It's in the bin folder of your java JDK install (Java SE). If you only have the JRE installed you probably don't have it.