i currently use the following script when i clone virtual machines. I've been using the same technique since the mid 90s when i was regularly cloning debian boxes to act as gateway/firewall machines for schools.
# change hostname of virtual machine from "$1" to "$2"
echo "Usage: $0 OldName NewName" >&2
[ -z "$OLD" -o -z "$NEW" ] && error
find /etc -type f -print0 | \
xargs -0r grep -l "\b$OLD\b" | \
egrep -v 'ssh|\.db' | \
xargs -d "\n" -r sed -i -e "s/$OLD/$NEW/g"
there are a few manual changes as well that i haven't got around to automating yet, mostly because i don't do it often enough that it's worth spending the time to figure out.
if the cloned machine has hard-coded IP address(es) rather than DHCP, i edit /etc/network/interfaces.
edit /etc/udev/rules.d/70-persistent-net.rules so that the interface names (eth0 & eth1) get assigned to the correct MAC addresses (otherwise they'll get eth2 & eth3 because eth0 & eth1 are already defined).
delete and regenerate the host's ssh key.