The Android Java SDK is nice and all, but what if you want to run some C service or code? Well, it turns out that this isn't exactly difficult. You can compile an application using a standard Linux cross-compiler, install it and run your programs from the shell.

You will need a cross-compiler (make sure you get the ARM GNU/Linux target). Then you can just create your program, compile, and upload to the device:

$ arm-none-linux-gnueabi-gcc -static hello.c -o hello
$ adb push hello/hello data/hello

You can then simply run you application:

$ adb shell data/hello           
Hello, Android!

Now of course, this doesn't at all explain how to tie into the graphics or the rest of the system, but that is left as an exercise for the reader ;)

Update: My instructions were missing the essential -static part!