Methods and apparatus for supporting network layer protocol version independent mobility management are described. In accordance with the present invention, the signaling method used to set-up the redirection (encapsulation or tunnel) is separated from the type of redirection being set-up. Through the use of a Protocol Independent Mobility Management Protocol and/or modules for implementing one or more aspects of the Protocol of the present Invention, Mobile IPv4 and IPv6 may run an top of any version of the network layer and can set-up tunnels of any network layer version over any other network layer version. Various features of the invention are used to establish tunnels which are capable of being used to commutate IPv4 and/or IPv6 packets (520, 530). Other features are directed to storing and using state information which allows IPv4 and/or IPv6 packets (520, 530) to be sent through a tunnel established using IPv4 or IPv6 type signaling (512).