The time it takes them to build/find a shelter depends primarily on:
The Environment
In mountainous terrain, it is easy to find pits, caves and gorges which the immortal can call home and settle in. In such regions, the immortal would gradually forsake the lower dwellings for a large underground cavern which protects him/her from the fury of nature (storms, hurricanes, landslides etc) and enables him a place for storing food.
In a jungle or lake habitat, the immortal would need to build cabins or dig deep pits in the ground and roof them up in order to make a secure underground dwelling.
Personal Strength And Mental Abilities
What if such caverns are already home to other (vicious) creatures such as tigers, bears, sabretooths (if you start them in prehistoric times)? Well it depends on you if the immortal can kill them or chase them away from such a hospitable place.
Overall
How long would it take the immortal to claim a suitable cavern or build a cabin/hut, you ask. Well it depends heavily on the physical strength of the immortal, his/her innovation and intellect. For example, a strong male immortal knowing the use of fire can chase away a pair of cave bears from a comfortable cavern while an immortal woman with strength equal to modern Asian women, not knowing the use of fire would find it impossible to even chase away a tiger from such a cavern.
With the strength and intelligence of a 20 years old person in our times and knowing very well what they require, have primitive woodcutting tools and are convenient with the use of fire, an immortal would take nearly 6 months to find and claim a cavern or build a rudimentary shelter in jungle/plains habitat.
Hunting Tools
The first stage of food awareness would be to learn which plants are edible and which are not. The next stage would be to learn which animals (including fish and birds) are edible. At this stage the immortal would primarily be a scavenger, feeding off scraps left by carnivores. As the knowledge of the immortal grows and his/her tool-making skills evolve, he/she will learn how to make rudimentary spears, and then (after several years) a primitive type of lance and archery equipment. He/She may also discover making blowpipes (provided the habitat has a lot of bamboo trees with long, straight stems).
Now we have an immortal who can hunt, fish and knows which plants to consume. How long would it take the immortal to reach this stage? Well, once again it depends on the innovation of the immortal, the habitat and the physical skills. For example, a strong male immortal with strength comparable to African males would probably be stuck with spear as the main offensive/defensive weapon and not invest time and energy in figuring out how to build a projectile weapon (bows and blowpipes) because the spear serves his needs very well. On the contrary, an immortal woman would quickly quit the spear in search of a weapon which she can use from range, hence forcing her to invent blowpipe or archery. For a 20 years old modern human, it would only take a day to start using a stick, a week to start sharpening one end for use as a spear and around 2-3 years to build primitive blowpipes or archery set.
Food Storage
Some environments allow for easy food storage. For example, in cold regions such as the arctic belt, you only need to bury your kill in snow to keep it from rotting. In warmer regions such as Africa and South Asia, you will require salting and sun-drying the meat to keep it from rotting. The same applies to storing seasonal fruits such as mango, apples etc. The immortal would strongly prefer storing dry fruits for their easy storage options. How long would it take for an immortal to discover food storage methods in warmer regions such as Africa? Well ... once again it depends heavily on the innovation and intellect of the immortal along with chance occurrences and luck. Maybe the immortal one day sees a dead deer in a pit on the coast line, buried in deposited sea-salt and finds out that its meat has not rotten. Maybe the immortal learns pickling methods from birds?
Agriculture
It is extremely hard to tell how long would it take the immortal to come up with the idea of growing edible plants as a food source. Maybe a very innovative and resourceful immortal gets the idea in the 20th year of his life. Maybe he never hits upon that idea. There are simply too many factors involved to sort this one out.
Herding Animals
Herding deer, goats, reindeer, camels, cows etc for food and milk is another idea which is very hard to tell if and when the immortal would hit upon. I personally think that while the immortal might discover agriculture ideas someday, it would be impossible for him/her to get the notion of herding animals and domesticating them. Why? Simply because the immortal has limited experiences and limited resources. He has always experienced that the deer and other herbivores would run away when he approaches them. What on earth would make him conceive the idea that he can gradually (over a period of hundreds of years) domesticate them? I think such a stage would never be achieved.
Domesticating Dogs/Tigers
This is actually easier than domesticating cattle and/or horses. Carnivores have lesser fear of man and if you keep feeding them, you can get them to get used to your presence. At first stage there would be a mutual bond of not harming each other (notice that this bond is formed between one dog/tiger and the immortal, not a group of them). The next stage would ensue, where the immortal feeds scraps of his food to the animal and trust gradually grows between them. In the third stage, the immortal and the carnivore would gradually come closer and be joined in a bond of loyalty and care. This is when the carnivore can be said to be truly domesticated.
Once a carnivore has been domesticated, the immortal can use it to gain a huge edge at hunting. But how long would it take for such a bond to form? Once the first stage has been reached (a silent agreement of not hurting each other), the rest would gradually follow. I would say that it would take the immortal around 30 years to gradually domesticate a wolf or tiger. At the first stage, there would be an animal which shares a pact of peace and its generations would gradually follow on to progress to second and third stages where they are convenient about hunting with the immortal as their pack member. Once such a stage has been reached, the immortal would have an easy supply of food.
Conclusion
All in all, the immortal would take nearly 40 years to reach a state where he/she has no longer to worry about food and shelter and can think about abstract ideas and start an effort to understand the world around him/her.
