Molecular motors are specialized proteins that perform active, directed transport of cellular cargoes on cytoskeletal filaments. In many cases, cargo motion powered by motor proteins is found to be bidirectional, and may be viewed as a biased random walk with fast unidirectional runs interspersed with slow tug-of-war states. The statistical properties of this walk are not known in detail, and here, we study memory and bias, as well as directional correlations between successive runs in bidirectional transport. We show, based on a study of the direction-reversal probabilities of the cargo using a purely stochastic (tug-of-war) model, that bidirectional motion of cellular cargoes is, in general, a correlated random walk. In particular, while the motion of a cargo driven by two oppositely pulling motors is a Markovian random walk, memory of direction appears when multiple motors haul the cargo in one or both directions. In the latter case, the Markovian nature of the underlying single-motor processes is hidden by internal transitions between degenerate run and pause states of the cargo. Interestingly, memory is found to be a nonmonotonic function of the number of motors. Stochastic numerical simulations of the tug-of-war model support our mathematical results and extend them to biologically relevant situations. © 2013 American Physical Society.