What do I need to get apartment

From the formalities standpoint, you need to find a place to stay first (even if it is only a temporary accommodation), then register with the authorities, and then open a bank account (banks usually require proof of residency, passport with visa, and proof of employment).
Finding a permanent place to stay will take time. Landlords will want to see you in person and you also should view any place before agreeing to rent it, so it makes no sense to start hunting for a rental place before you arrive. In addition, renting cycles are long, with a minimum termination notice period of three months and good places (at least in popular cities like Hamburg) advertised and snapped up soon after the previous tenant tenders his termination - thus you might have to sign a rental contract months before move-in. Therefore it is wise to arrange for temporary accommodation (hotel, B&B, or serviced apartment) for the initial period (up to three months). Landlords might also want to see your payslip, bank statement and other things showing solvency, so this method will give you time to arrange for those.

If I Want to register myself at the administration, knowing that I will start my job beginning in January, can I do the registration end of February for instance? Or do is it compulsory to register myself before I start my job? Or can I do it after I started the job? Thanks

It is mandatory to register with the authorities one week before or after you take up a residence in Germany. This is regardless of your work and you can be fined if you don't, or do it late.

When you say residence, what so you mean? Does this implies permanent apartment or Even a temporary accommodation?

The trick is that I will start my job in January. I would like to know if I can already register myself and my wife, who is Colombian and need a residence permit in October while I am still working in Danemark (where I currently work) or if I need to register myself and my wife only when I will have quit my current job?

As far as I know (please confirm this with the authorities!), residence is any place you stay at for more than a week (while holding a residence visa - not a tourist visit visa or similar). You need to register with the authorities within a week before or after moving in. This really has nothing to do with your job or when it begins!

But Then can I register myself to the authorities even if I am still working in denmark? Or do I Need first to stop working in denmark?

Once I am register, I have three months to go to the immigration service to say I am Staying more than 3 months, is it correct?

One more (last) time:
Registration of your residence has NOTHING to do with work!
You need to register when you take up a residence, regardless of whether you work or not. Residence is a place to sleep, eat, live - e.g. a rental (or temporary) apartment.
If in doubt, consult the relevant authorities (Einwohnermeldeamt/Bürgerbüro) or read the regulations (Bundesmeldegesetz).

I would like to confirm that even if I continue to work and live in Denmark until end of November, I am able to register myself in Germany beginning of November. I could get a tempory accomodation just for registration time. Because I will inform the danish citizen service that I want to be deregister from Denmark end of November when I stop to work in Denmark. However can I be deregistered from Denmark end of November and be in the same time register in Germany beginning of November?

I see no problem there, as it is perfectly fine (and legal) to have several registered residences at the same time. But please confirm this with the relevant authorities (especially in Denmark - I can only tell about Germany!).
Please note that some cities (i.e. those with a housing shortage) charge an extra second residence tax (Zweitwohnungssteuer). I don't know if Hamburg does. Inquire!

so it would be legal to still continue living and working in Denmark as resident (resident for more than 3 months) and do the registration in Germany?

But what I don´t understand is that the registration in Germany is to say that I will stay more than 3 months in Germany right? But I cannot be registered in two countries stating that I am staying in this two countries more than 3 monts.

First, the German authorities do not care about formalities in other countries. So if you take up and register a residence here, it is for the German office your main and only residence.
Second, when registering you do not need to state how long you will stay there, or if at all. The need to register is triggered by you having a residence at your disposal - even if in the end you never live there. I was for years living in Asia, but needed to be registered in Germany because we kept our house there, despite maybe visiting only two weeks per year!

Hi

I already have a job contract. But I will work and live in denamrk until January when I will start my new job. However I need to register my wife and I in Germany in November. So I need to get a residence in Germany and apparently I could give an hotel adress. But I wand to understand if I can register in Germany giving an hotel adress even if I will stay in an hotel only one or two nights and then I go back to denmark until January?

Again (and this is REALLY the last time - even if you are not smart enough to grasp the rules, you should nevertheless follow them meticulously to avoid trouble):
You MUST register if you have a residence available to you in Germany. A residence is a place to stay and live. It does not matter whether you actually stay there or not, or where you work.
You CANNOT register if you do not have a residence, a place where you COULD stay.
A hotel can be a residence if you have booked a room there for the duration of your registration, which is available to you at any time. Just staying there for a few days and then giving up the room (as you probably plan, for cost reasons) will not work.

Another aspect you didn't mention, but should consider, is tax: The moment you take up a residence you become tax-liable in Germany with your world income. There might be tax treaties with Denmark or your home country that minimize the chance of double taxation, but in any case you must submit a yearly tax declaration in Germany stating your world income and show proof that it is covered by a treaty (and that you pay tax on it elsewhere). This is onerous and might break your plans..

This is very clear. Thanks a lot for the help and my apologizes for any inconvenience

You posted the same again in another thread. Do you not understand or not believe me?
Please contact the registration office to get definitive informatin!

What Beppi has said is 100% correct. If you live in Germany then you MUST register the fact - think you actually have two weeks to do it - but nontheless sooner the better.  All things said - just contact the registration office and they will put you straight,

Good luck..