Cross-Compiling for an embedded ARM-based Linux system

I try to compile some C code for an embedded (custom) ARM-based Linux system. I set up an Ubuntu VM with a cross-compiler named arm-linux-gnueabi-gcc-4.4 because it looked like what I needed. Now when I compile my code with this gcc, it produces a binary like this:

$ file test1
test1: ELF 32-bit LSB executable, ARM, version 1 (SYSV), dynamically linked
(uses shared libs), for GNU/Linux 2.6.31,
BuildID[sha1]=0x51b8d560584735be87adbfb60008d33b11fe5f07, not stripped

When I try to run this binary on the embedded Linux, I get

$ ./test1
-sh: ./test1: not found

Permissions are sufficient. I can only imagine that something's wrong with the binary format, so I looked at some working binary as reference:

$ file referenceBinary
referenceBinary: ELF 32-bit LSB executable, ARM, version 1, dynamically linked
(uses shared libs), stripped

I see that there are some differences, but I do not have the knowledge to derive what exactly I need to fix and how I can fix that. Can someone explain which difference is critical?

Another thing I looked at are the dependencies:

$ ldd test1
    libc.so.6 => not found (0x00000000)
    /lib/ld-linux.so.3 => /lib/ld-linux.so.3 (0x00000000)

(Interestingly, this works on the target system although it cannot execute the binary.) The embedded system only has a libc.so.0 available. I guess I need to tell the compiler the libc version I want to link against, but as I understand it, gcc just links against the version it comes with, is this correct? What can I do about it?

Edit: Here's the Makefile I use:

CC=/usr/bin/arm-linux-gnueabi-gcc-4.4
STRIP=/usr/bin/arm-linux-gnueabi-strip          
CFLAGS=-I/usr/arm-linux-gnueabi/include             
LDFLAGS=-nostdlib
LDLIBS=../libc.so.0

SRCS=test1.c
OBJS=$(subst .c,.o,$(SRCS))

all: test1

test1: $(OBJS)
    $(CC) $(LDFLAGS) -