Hi Ludwig,
When I learn a piece--slowly, as slow practice is essential--I watch every detail like a hawk. (When studying with a teacher, some people, not all, become lazy and wait for her to point out any mistakes. When you study alone, you have a serious obligation to do all that for yourself, as an obligation to the composer and the art.) I start with the notes and rhythm. Then I pay more attention to phrasing details. Voice leading and chord voicing become important here too. Next, I start to bring in all the dynamics. I save pedaling until this later point, because in learning at first, I want the fingers to do all the work without the pedal. As I'm doing all this, I keep fingerings somewhat tentative. I can't tell you how often, in first learning a piece, I believed I had the best fingering for a passage only to discover a better one later on. And yes, a new fingering always means relearning the passage and breaking and reestablishing habits.
I make this approach l sound quite "linear", but only to show a general thought process. Actually some of these things are happening in tandem as opposed to a strict and precise sequence. Once I can articulate the piece, then I concentrate on matters of interpretation and its finer points.
If I pick up a piece by Chopin, Debussy, Rachmaninoff, etc. I already know how it generally "goes", so I don't need a recording as a crutch to steer me through the learning process. (When I was young and less familiar with the repertoire, I did need that crutch more often though.) Right now, if I were to study a complex piece with which I was truly unfamiliar, or a seldom heard piece of a well-known composer, in a case like that I might listen to a recording first, rather than waiting until I had the piece completely playable. But those would be the exceptions, not the rule.