Well, I've heard self proclaimed libertarians say things like "taxation is theft of private property". So that's what I'm basing that on.

Most libertarians I've talked to at least see the role for a minimal state. That state does manage external threats and contract enforcement. I can't imagine those being free things, so at least some taxes would be necessary.