What does the speaker mean when he speaks lines 58-61 of "The Seafarer"?

"The Seafarer" is an Anglo-Saxon poem which was probably originally sung by scops, like most of the other literature of the period. It has been translated many ways, so an examination of several translations should reveal and confirm a complete answer to your question.

Line 58 of the poem is a natural starting place, but line 61 comes in the middle of a thought, so I included the next few lines, as well, in order to get a better idea of what the three lines you mention might mean.

The poem, or at least the first half of it, is a seaman's lament about living his life at sea. He is cold and miserable, lonely and alone, and when he is on land he dreads going back to the sea. 

Lines 58-64 are the last lines in which the speaker talks only about his relationship with the sea; after that he turns to more religious and philosophical discussions. The rhetorical question he asks right before the "and yet" answer in line 58 is this:

            Who could understand, 
            In ignorant ease, what we others suffer 
            As the paths of exile stretch endlessly on? 

Who, the speaker asks, can sit in their homes (on dry land) and claim to understand what the seafarers ("we others") suffer as their "paths of exile [loneliness and suffering] stretch endlessly on?" In other words, no one but another seafarer could possibly understand how bad this life really is.

The answer to this rhetorical question ("and yet") follows, and Burton Raffel translates it this way:        

            And yet my heart wanders away, 
            My soul roams with the sea, the whales’ 
60        Home, wandering to the widest corners 
            Of the world, returning ravenous with desire, 
            Flying solitary, screaming, exciting me 
            To the open ocean, breaking oaths 
            On the curve of a wave. 

Despite the hardships, suffering, and sacrifice of living at sea, this seafarer's heart is happiest when he is on the sea. Look at the language and imagery--"wandering," "ravenous with desire," "exciting me," "the curve of a wave"--and note that there is nothing here but beauty and desire. No cold feet, no harsh winds, no crushing loneliness which he talks about earlier in the poem.

A perhaps more authentic translation reads this way:

And now my spirit twists

out of my breast

my spirit

out in the waterways

over the whale's path

it soars widely

through all the corners of the world--

it comes back to me

eager and unsated;

the lone-flier screams,

urges onto the whale-road

the unresisting heart

across the waves of the sea.

The language and imagery in this translation also implies a light heart, a joyful spirit, and a love for the sea. 

These lines, then, are the great reversal of the poem. What was lamented by the seafarer as being such an awful and miserable existence has now, upon reflection, become a lofty, soaring adventure of which he never tires.