I get the error "In order to perform this operation a successful bind must be completed on the connection."

/shrug

Yes, some AD servers may (as far as I know) not be set up to allow anonymous queries, even just to get the initial namingContext information.

A bit of terminology first - in LDAP (which is what we're talking here), "bind" simply means to authenticate yourself to the server. LDAP simply decided for some reason to introduce a new term for this - binding. Most things just say "login" or "authenticate".

So what it's saying is that you must authenticate.

The flags to ldapsearch you need to know are:
-x -- bind with simple authentication (not SASL)
-W -- prompt for the password for simple authentication
-D <blah> -- bind as this Distinguished Name (DN)

So you have to use -x to use simple bind, and -W to tell it to prompt for a password - AND "-D" and your DN to tell it your username.
Usernames in LDAP are DNs - Distinguished Names.
They include your short username (eg bob), and also the DC components of your organisation - eg "dc=company,dc=com" where "company" is the company name that LDAP uses for your company.
Unfortunately, you have to know this information in advance.
It's possible that it may also require an OU component - Organisational Unit.

So the extra flags you need to add to the ldapsearch given in this hint are:

ldapsearch -x -D "cn=myusername,ou=something,dc=mycompany,dc=com" -W

... and then the rest of the stuff in the ldapsearch in the hint.