I used to tutor, and I have a terrible sense of direction, too.

It's important to notice distant landmarks, first of all. For example, in my city I know that the mountains are to the north.

Start learning the major streets, what's on the streets, and how they cross each other. You can try learning one street at a time. As in, "That's the street the Target is on. Oh, and there's the McDonald's too. If I keep going south, the street changes names." etc.