Well the way I wrote my pipes solver was to keep a set of possible orientations of every tile and gradually remove impossible options by using border conditions and some heuristics like avoiding islands and loops. And when this doesn't turn up any new info I resort to depth-first search.

The generator basically does the same but every tile starts out with a full set of possible orientations - every rotation of every tile shape (there are 62 I think). I remove some orientations due to border conditions, then pick a random possible orientation for some tile and so on till the board is filled. There usually is some backtracking involved.

This isn't terribly efficient and can get stuck for quite long when generating large puzzles. I actually want to look into adapting maze generation algorithms for creating these puzzles, so thanks for the link, I'll check it out.