Traffic analysis (TA) is a useful tool aimed at understanding network traffic behavior. Basic network administration often takes advantage of TA for purposes such as security, intrusion detection, traffic shaping and policing, diagnostic monitoring, provisioning, and resource management. Network flow watermarking is a type of TA in which packet features of selected flows are manipulated in order to add a specific pattern easily identifiable when the watermarked flows cross an observation point. While passive TA has been extensively studied with hundreds of papers found in the literature, active TA, and more specifically network flow watermarking, has only recently attracted attention. Enforced robustness against traffic perturbations due to either natural network noise or attacks against passive TA have enhanced the appeal of this technique. The contribution of this paper is a thorough review of the main watermarking algorithms implemented for traffic analysis purposes. We present an overview of the motivations and the objectives that have led to the use of network flow watermarking. We also describe the general architecture of a watermarking system. In addition, we impose clarity and order in this branch of TA by providing a taxonomy of the algorithms proposed in the literature over the years, and categorize and present them based on carrier, visibility, and robustness.