The simplest way into Deadwood (or west deadwood at least) is by swimming east in the river and then swimming south when you see the tiny shore.

To get to eastern Deadwood, turn your lantern and enter the door/cave that is between the two shops. Theres also another lantern cave entry at the furthest south-east point of swamptown.