The term was coined by anarcho-capitalist Lew Rockwell in 1999, wanting it to refer to pre-war, traditional libertarianism as opposed to the more socially progressive "Beltway libertarianism". Ironically Rockwell stopped labeling himself a paleolibertarian when the term started to refer to socially conservative libertarians.
Keep in mind that though paleolibertarians are opposed to a large federal government by being strongly in favor of state's rights, many are in favor of social authoritarianism on a state and local level, meaning that they may be considered, like Ron Paul, more anti-federalist than "small government" libertarian. (Indeed, one of the primary beefs many of them have with the federal government is that said federal government is seen as interfering with their God-given right to lord it over their local subalterns as they see fit.) The degree of social authoritarianism they are in favor of varies from paleolibertarian to paleolibertarian, though some are even more extreme than some of the Republican Party by tolerating or even encouraging anti-Sodomy laws or being sympathetic to the Lost Cause of the South.
Known individuals within the liberty movement to have shown tendencies towards paleolibertarianism include failed Republican presidential candidate Ron Paul, conspiracy theorists Alex Jones and Mark Dice, and Australian liberty activist Anthony Coralluzzo.
 Libertarianesque and very, very paleo
Libertarians believe strongly that the federal government should stay out of everyone's personal affairs. Some in the paleolibertarian camp believe this includes the idea that the federal government legally cannot (a la the 10th amendment) and that the state government should not outlaw or restrict corporal punishment in the home, and that, more broadly, the head of the household should be free to run the affairs of the household exactly his way without the government having any right to restrict him in any way.
Many paleoconservatives, like Phyllis Schlafly, believe that a husband has the right to rape his wife because a married man has the right to demand sex from his wife. Necessary for this "freedom" is the legal inability of the government to criminalize married rape.