make them large enough to have their own gravity (think planet sized) and then put huge rocket boosters on them to separate at will.
Just kidding. =) Have you looked at something as simple as a trailer hitch? Just get a ball and cuff and put a servo on the little flip piece to lock the ball in. Loop and hook? How about putting a large screw on the end of a motor shaft and a nut on the other robot? Electro magnets? Permanent magnets with an ejection piston?
What kind of hold strength do they need? Does a com bus need to be established over this physical link or will it communicate wirelessly all the time? Will they always be on flat terrain, will there be obstacles?