PITR/Online Backups? When can I delete archived WAL logs?

Ok.  I have been going over the documention for PITR/Online Backups,
and it has me confused about a couple of things.  Hopefully someone
can help me. :-)

First of all, here's what I'm doing:

-- from psql
SELECT pg_start_backup('mylabel');

-- from shell
rsync --exclude $WALARCHIVEDIR $PGDATA remotehost:/dir/to/pgdata
# ignore the fact that WALARCHIVEDIR is not a real var.. it's defined
correctly in mine :-)

-- from psql
SELECT pg_stop_backup('mylabel');
rsync $WALARCHIVEDIR remotehost:/dir/to/pgsql/archive

When I do this, and throw a recovery.conf into place, it generally
spits out errors like this on the other box if I attempt to start with
this:

cp: /usr/local/pgsql/archive/00000001.history: No such file or directory
cp: /usr/local/pgsql/archive/00000001000000000000000F: No such file or directory

Do I need to backup pg_xlog?  I could have sworn it said not to.
Also, am I doing this right at all?  Does anyone have a script they
are using for this?

Thanks in advance,
Jason DiCioccio