First of all, how exactly do you entangle two atoms? I've heard about how they entangled atoms in quantum Teleportation experiments, but I don't get how they did it. I've heard that the atoms must "interact", but what exactly does that mean? Do they have to touch? Do they have to be within a certain distance - like a foot or an inch - from each other?
Atoms can interact in a variety of ways, it varies from experiment to experiment.
In principle two qubits with spins 1/2 could interact via magnetic force. In this case they would have to be extremely close. This experiment would also be extremely hard.
An easier way would be to use ensembles of atoms. Atomic beams can be prepared where atoms are held in place by electromagnetic fields. In this case we cannot force each atom to interact, but measure the ensemble properties. This is done routinely in Bose Einstein Condensate experiment which can interfere two atom beams.
Another relatively easier way is to keep the atoms static and use light to mediate an interaction between the atoms. One can engineer a system such that the two atoms "interact" using photons. Usually this requires either detection or generation of states of light coming from or towards the atoms, therefore using nonclassical light to generation atom entanglement. The advantage of this state is that the atoms don't have to be together at all as shown in this recent paper by Reiner Blatt at University of Innsbruck.