This on my x86_64 box:

  $ echo 'int main(){return 0;}' > test.c
  $ gcc -static -o test test.c
  $ ls -l test
  -rwxrwxr-x  1 andy andy 559884 Sep 27 16:37 test

Glibc's notion of the world includes half a megabyte of omnipresent
static... stuff.

See bug 169412 for a practical problem related to this.

I tried stuff like linking against malloc() and printf() (perenial
"big chunk of libc" entry points) and the size grew by only a few tens
of kilobytes.  Something is pulling in *far* more than it should.
Static linking isn't often necessary or useful, but it should at least
be possible without wasting 500k for every binary.