I don't know if it's "supposed" to feel like anything in particular, but it may take some time to develop the mind/muscle connection if you're unused to specifically activating the deadlift muscles.
It also matters which style of deadlift you're doing, for example, there are differences between stiff-legged deadlifts (erectors, hips, butt, some thighs) and "traditional" deadlifts (same plus a bunch more, great overall exercise).
You'll also want to make sure your form is pretty dead-(lift)on, you're "blocking" appropriately, and so on. Having someone to work with when doing an exercise like the deadlift is pretty important since the risk of a back injury is greater than with a lot of other exercises--slipping a disk is unpleasant, I'm told.
That you're ending up feeling pretty worked leads me to believe you're doing "traditional" deadlifts. Since it's an-almost-entire-body exercise, you won't necessarily feel the "I'm working this specific muscle" feeling you get from more-targeted movements like the bench or squat.