I haven't smoked it, but others have said that the aforementioned Count Pulaski has a distinct licorice/anise flavor, while in many of the blends roth mentions, the anise/licorice hides its usual flavor and takes on a different character in combination with the different tobaccos.
Fusilier's Ration, for one, almost certainly has a good bit of anise in it, but it gives the blend an overall sweetness rather than a real anise-flavored kick.
For what you're probably looking for, try Count Pulaski or one of the burleys roth mentioned from Uhle's.