En movistar al menos (es el caso que conozco), hacen como cuentan por ahi, fotocopian tu dni, obtienen los datos de tu tarjeta del telefono y firmas en una tableta electronica. Tras eso, te dan un impreso indicando que tu número está registrado. Además recibes de movistar un mensaje indicando: "El número de telefono XXXXXXX ha quedado registrado a nombre de XXXXXXXXX", donde las X son tu número de teléfono y tu nombre.
También esto es personal, o sea, que si vas a registrar el telefono a nombre de alguien, tiene que ir esa persona, por ejemplo, si lo vas a registrar a nombre de tu novia, no vale con que vayas con el dni de ella, tiene que ir la persona en cuestión a nombre de la cual se registre su teléfono, y con el dni o algun otro documento acreditativo.