Does this proof use Axiom of Choice? 
Here is a question from Munkres Topology:
   and here is its solution:
  

I think that while choosing $b_1,b_2,\dots$ we are using Axiom of Choice. But again, since for each $b_n$ we are 'choosing' only one element from a nonempty set, I think we do not have to apply Axiom of Choice.
I am confused!

Since the integers are countable, we can enumerate them as use that as a choice. But for the negative integers it's even simpler. Just go down the order of the integers. 
For a general linear order, though, this would require some choice. So you are right to be skeptical. 
Do note, though, that just choosing one element from a set can be misleading. If you end up potentially choosing from infinitely many sets (each choice requires you that the next choice is from a smaller set) then the axiom of choice might still be necessary. 
