The seagull is an average and ordinary bird, not to mention an annoying one when it tries to steal your lunch on the beach. It's not some majestic creature like an eagle, a nasty one like a vulture, or even a funny-looking one like a pelican. But it makes sense that Crane would use such a common bird as a symbol of freedom. Throughout the poem he tries to redeem the value of ordinary and anonymous things.
Also, Crane is making an allusion to Walt Whitman's "Crossing Brooklyn Ferry," another classic poem about crossing from Brooklyn to Manhattan, but written before the Brooklyn Bridge was built. Here are some of the lines from Whitman's poem:
I watched the Twelfth-month sea-gulls—I saw them high in the air, floating with motionless wings, oscillating their bodies,
I saw how the glistening yellow lit up parts of their bodies, and left the rest in strong shadow,
I saw the slow-wheeling circles, and the gradual edging toward the south.