The biggest difficulty with getting into Touhou is the number of characters which are present. The bulk of the canon story material is really not that large.
The main Touhou games are released in chronological order. This is rather irrelevant because the stories typically are not closely related anyway. However, newer games do involve characters from older games. This shouldn't really stop you from understanding what's going on, because the characters are all pretty easy to understand, but you may miss a few things if you go out of order. Note that these are really essential to understanding Touhou well, since they serve as the introduction for most of the characters and almost all of the major plot points which are referenced elsewhere are from the games.
Typically, it's recommended to start with the beginning of the Windows Touhou games, Touhou 6 (Embodiment of the Scarlet Devil). The Windows Touhou games have only occasionally used characters from PC-98 era games, apart from Reimu and Marisa (the protagonists). However, it would not really hurt anything to start with any of the other games either. If you find the games too difficult, many people who are just interested in the story watch replays of them online or read transcripts of the dialogue (which are available on Touhou Wiki, e.g. here). There are fan-made patches available for all of the main Touhou games.
If you want an official source, Bohemian Archive in Japanese Red (the first Touhou fanbook) has a great deal of information on the characters up to Touhou 9. Touhou Wiki typically serves as a fine alternative as well, though it has a lot of fanon as well. Neither of those are really stories though. To be perfectly honest, you can read almost any of the canon manga releases if you're willing to occasionally look up who a character is. Inaba of the Moon and Inaba of the Earth might be a particularly good choice simply because it only involves a small number of characters.
In any case, once you know the very basics (the major characters and plot of the main games), you can pick up pretty much anything canon or fanon with relative ease. The biggest difficulty is just learning all the characters in the first place, and I don't think there's any better advice for that than just to play the games (or at least read the dialogue from them).