This question is very broad and there are many reasons for how the Nazi party were popular in Germany. Examples include their use of propaganda, most specifically their rhetoric of the 'volksgemeinschaft', meaning the 'people's community.' Examples of this include the Hitler Youth, which began as a voluntary youth group, but became compulsory as the decade wore on and Germany geared up for war, eventually enrolling more than 9 million young Germans.
Aside from propaganda and public campaigns, the Nazi party were also successful through forceful campaigns. During the Night of the Long Knives in 1934, many enemies of the party were purged, specifically in the Jewish community. This is an important distinction, as the question asks about "hearts and minds", you have to consider ways they won genuine support, and others where they forced it. They used equal tactics of coercion and brutality in order to win over the public, and remove their enemies or those they deemed 'undesirable to society.'