Lets say you have n items and know you want to mark m items, m<=n (according to the % value). Now you mark the items one-by-one, starting with a random probability of m/n for marking the first item. But instead of keeping that probability fixed, after each step you adapt the actual probability to what is needed now!
So when after k steps you have marked l items, you will have to process (n-k) remaining items, and you want to have (m-l) of them marked. So choose the probability of the next item as (m-l)/(n-k).
As you see, the more l approaches m, the smaller the probability of marking will become. When l is equal to m, the probability is 0. On the other hand, when the number of remaining items reaches the number of remaining items to marked, the probability will become 1. Finally, you will end up with exactly m marked items.
It should be obvious that the run time is O(n), since each element is processed once, and the only thing you have to keep track is the both numbers (m-l) and (n-k).