Om du vet hur man jobbar med sessions-variabler så hade jag valt det istället.
Typ, du lagrar hela tiden vart du är någonstans, ex:
<?php
$_SESSION['gender'] = "man";
$_SESSION['category'] = "badbyxor";
?>
<a href="site.se/?gender<?php echo $_SESSION['gender']; ?>&category<?php echo $_SESSION['category']; ?>">LÄNK</a>