You can generate stealth XP as soon as the game starts by crouching (stealth mode) and entering areas that you’re not supposed to be in. For example, at the inn in Skalitz there are two rooms where it tells you, the moment you enter the room, that you are entering an area that does not belong to you. If you sneak into one of those rooms and then look at your Stealth XP, you will notice it has gone up by a slight amount. Within that room, it doesn’t matter what you do as long as you have snuck into the room you get the same amount of XP. In other words, movement within a room does not increase XP, it is the fact that you snuck in that granted you the XP. There are two such rooms in the inn. Sneaking back and forth between those two rooms will see your Stealth XP go up a small amount each and every time you enter one while sneaking.
As others have mentioned, opening locks while sneaking (which you can do as early as Talmberg as soon as you flee Skalitz - the vendor (Voteva?) in Talmberg castle sells lockpicks and buys all stolen goods) will also grant you Stealth XP as will sneaking behind anyone and using the Knockout option. Hilariously, as a test I knocked out Kunesh while I was in Skalitz and took everything he owned, just to see if that worked. It did and I got a significant chunk of Stealth XP for doing it. Some time later, I see Kunesh come walking down the road in his underclothes and coming straight toward me, well outside of his normal AI behavior. He walked straight up to me, looked me in the face and said, “What the hell?” and then turned around and walked away. I laughed so hard I almost pissed myself.