I get upgrades in fits and starts. For example, sometimes I'll tackle a few dungeons without going on any side-quests at all, but then I'll go on an exploration rampage and get as many extras as I can find before progressing with the story. This also depends on the kind of play-through I'm on, too. That's what I'm like the first time through; on subsequent play-throughs, I already know where many of the upgrades are, and I grab them when I'm conveniently near. If I know the game really well (say, OoT) I plan out in my head what order I'm going to do things in: which upgrades to get on the way to which dungeons, when to go out of my way for other extras, things like that. However, I sometimes do minimalist runs (where I only pick up what's needed for the quest, take extra heart containers from bosses, and don't use any health items), or three-heart runs (no extra hearts, of course) or a combination of the two. When doing those I'm either limited on my upgrades or I don't get them at all.
Anyways, as I said, I prefer to get them on the way. However, I never usually get every single one on my first play. In fact, I think I've only 100%ed two games: MM and MC. Well, and LoZ and AoL, but those are so easy to do that with they hardly count.