You probably don't want to wait a set amount of time - it will make your tests slow. You would ideally want to continue as soon as the record is added. You can use Geb's waitFor {} to poll for a condition to be fulfilled.

    // Second Test
    def "should find record named myRecord"() {
        when:
        to SearchPage

        then:
        waitFor(30) {
            search_query = "myRecord"
            searchButton.click()
            //verify that the record was found
        }
    }

This will poll every half a second for 30 seconds for the condition to be fulfilled passing as soon as it is and failing if it's still not fulfilled after 30 seconds.

To see what options you have for setting waiting time and interval have look at section on waiting in The Book of Geb. You might also want to check out the section on implicit assertions in waitFor blocks.

If your second feature method depends on success of the first one then you should probably consider annotating this specification with @Stepwise.