Sort a scrambled itinerary (Google apac test problem)
Style notes:


The Ruby convention is 2 spaces of indentation
Use braces for single-line blocks, but do...end for multi-line blocks. 
Keep the block parameters on the starting line; i.e. don't do this

(1..num_cases).each {
    |num|

Use #nil? rather than == nil, empty? when checking array lengths, #first/#last when accessing the start/end of an array, etc.. 
Postfix conditions for single-line, single-branch conditionals. E.g. this:

if arv == nil 
    break #Done if we are out of tickets
end


becomes:

break if arv.nil? # Done if we are out of tickets

Instead of iterating through ranges like (0...n) you can use n.times instead. E.g. n.times { |i| puts i } will produce the same as (0...n).each { |i| puts i }
You missed a single pair of parentheses in a method call: .join ' ' :)
Granted, you can write Ruby without parentheses (Seattle style Ruby). Personally though, I like 'em (except for puts and print), but there are arguments for and against.


Code notes:

Instead of $stdin.readline.strip, you can use the more common gets.chomp. #gets is just a shortcut for $stdin.readline, and #chomp chops off the linebreak, but leaves other whitespace intact.

When possible use methods like #map and #reduce and their ilk instead of modifying a closed-over object from inside a block. E.g. this:

tickets = {} 
# ...
(0...num_flights).each {
    tickets[$stdin.readline.strip] = $stdin.readline.strip 
}


can be written in a few different ways - #each_with_object is probably the cleanest:

tickets = num_flights.times.each_with_object({}) do |_, tickets|
  tickets[gets.chomp] = gets.chomp
end


Alternatively, you could read the lines, and chunk them up afterward:

lines = (num_flights * 2).times { gets.chomp }
tickets = Hash[ lines.each_slice(2).to_a ]


You can do something similar in #print_flights instead of using step(2):

def print_flights(case_num, ordered_flights)
  tickets = ordered_flights.each_slice(2).map { |pair| pair.join("-") }
  puts "CASE ##{case_num}: #{tickets.join(" ")}"
end


Typically, Ruby coders avoid "raw" array indices and index arithmetic like array[i+1] in favor of more expressive code.

Lastly, #order_flights has side-effects: It deletes entries from the tickets hash you pass to it. Sure, it doesn't matter for this particular exercise, but side-effects are side-effects and should be avoided.



The algorithm itself looks fine to me. I might write it like so:

def read_tickets
  count = gets.chomp.to_i
  count.times.map do
    [gets.chomp, gets.chomp]
  end
end

def sort_tickets(tickets)
  flights = tickets.dup # make a copy to modify
  stops = flights.shift
  until flights.empty?
    from, to = flights.shift
    if from == stops.last
      stops.push(to) # could also use &lt;&lt;, but #push keeps "symmetry" with #unshift
    elsif to == stops.first
      stops.unshift(from)
    else
      flights.push [from, to]
    end
  end
  stops.each_cons(2).to_a
end

case_count = gets.chomp.to_i
case_count.times do |t|
  tickets = read_tickets
  ordered = sort_tickets(tickets).map { |ticket| ticket.join("-") }
  puts "Case ##{t+1}: #{ordered.join(" ")}"
end


Pretty much the same algorithm, just written differently. Notice however that I never actually use hashes, just nested arrays. Unfortunately, it's sloooow (the else branch and #each_cons are probably to blame, but I haven't checked). Still, style-wise it might give you some ideas.

An alternative, which does use hashes, would be to scan the tickets to find the first leg of the journey. After that, a single loop through should put them in order.

def read_tickets
  count = gets.chomp.to_i
  count.times.each_with_object({}) do |_, tickets|
    tickets[gets.chomp] = gets.chomp
  end
end

def print_sorted_tickets(tickets)
  inverted = tickets.invert
  from, to = tickets.detect { |from, to| inverted[from].nil? } # find first
  print " #{from}-#{to}"
  while tickets[to]
    from, to = [to, tickets[to]]
    print " #{from}-#{to}"
  end
  print "\n"
end

case_count = gets.chomp.to_i
case_count.times do |t|
  print "Case ##{t+1}:"
  tickets = read_tickets
  print_sorted_tickets(tickets)
end


I've combined sorting and printing only because I can. I'd prefer sorting and then printing, like above, or at least returning a string. The code can easily be changed to support that, but I figured I'd try combining the two. And this runs about as fast as your solution (somewhat surprisingly - I figured #invert would be more expensive).

By the way, one could "manually" create the inverse hash immediately when reading the input, instead of using #invert. But I don't think it'll make that much difference. Either case would be trading memory for simplicity.