It's about 500 metres to walk from Teviot to the Cowgate Tourist Hostel following these instructions. You can also walk there via the other sponsored hostel, Budget Backpackers.
Head out of Teviot and across/round Bristo Square
Walk past the buildings
Round the corner
Through the underpass
Down West College Street
Down the steps straight ahead or down Guthrie St to the right
Out from Guthrie Street to the Cowgate
Turn left
And you're there!