The earliest written instance I can find is F. C. Adams, Manuel Pereira (1853)
The old fellow laughs at the joke, as he calls it, and tells 'em, when they stick it to him, they don't understand the practice of making money.
Reading the context (be warned, it's a bit unpleasant) I'd be pretty sure the meaning there is when they bring the matter up to make fun of him (that's to say, when they give him stick about it).
In modern usage, to stick it to someone (often, to the man, representing the establishment) tends to imply attack strongly, vehemently - usually through words or defiant actions, rather than direct physical assault. But give someone stick usually means to tease them (playfully) about something.
But that divergence doesn't see to have happened until much later. The earliest use I can find for give someone stick is a completely "literal" one - Theodore Winthrop, John Brent (1862)...
Alas! only the perverted donkey, bristly and incorrigible, came under my tutorship. I was too humane to give him stick enough, and so he mastered me.
Doubtless someone else can do better, but the earliest instance I can find for give stick = tease is someone using the nom-de-plume "Flame", A Life on the Game (1984)...
The strange thing was that when the kids used to give me stick about it, I never felt ashamed.
In short, it seems metaphorical stick it to him predates give him stick by a considerable period. And the tease subsense seems to have migrated from the former to the latter. But it's also worth noting that whereas the "victim" being given stick usually feels quite wounded, sticking it to the man often implies nothing more than a symbolic defiant gesture that the establishment doesn't even notice.
In case my above text doesn't make it obvious what I think stick alludes to in these contexts, I'll just say that so far as I'm concerned it's basically beating with a stick, but probably influenced by poking with a [sharp] stick (as in bleed like a stuck pig).