stab?  =)

this will not work if "noise" contains any whitespace.  (I'm not sure
if it can or not - like you said, it was vague.)

The ? makes the * a "reluctant quantifier".  Together, *? means the
smallest number of repetitions necessary for a successful match, and it
is a concise way of solving the type problem you raise.  Unfortunately,
it needs help to work in a situation where the opening and closing
delimiters are different.  Understanding why that's the case goes hand
in hand with finding a solution; the key here is that the regex engine
works from the left, and only backtracks when it absolutely has to.  In
the example, the regex engine latches on to the first 00 as the start of
the group, and never has to backtrack (to start the group at the second
00 instead) because it can obtain a complete match without doing so.

Here's an example of a pattern that works:
    Pattern pat = Pattern.compile(".*(00.*?01) target_mark");
    Matcher matcher = pat.matcher(
            "00 noise1 01 noise2 00 target 01 target_mark");
    if (matcher.matches()) {  // or .find() or .lookingAt()
        System.out.println("The pattern selected this group: '"
            + matcher.group(1) + "'");
    } else {
        System.out.println("The pattern did not match");
    }

Output is:
The pattern selected this group: '00 target 01'

*Why* that works is left as an exercise for the reader :-)

Extra credit: is the reluctant quantifier necessary in the above
pattern?  Would a greedy ("normal") one do the job as well?  (Hint:
yes.) Why or why not?

And that one does the job for the sample data too, though it can fail if
the target or noise is permitted to abut the 01 delimiter without
intervening whitespace.