Does the LDAP module encrypt directory queries? I'm using the LDAP module and do not have the Start-TLS box checked. Does this mean my directory queries are running over an insecure connection? Or are queries to the directory server always ran over SSL/TLS?
As configured in your screenshot -- yes your queries are running in plaintext over the wire. This is similar to running MySQL on the default port and not running MySQL connections under SSL (which is also possible by sharing certs).

Securing network connections between Drupal and LDAP is dependant on your LDAP vendor. For instance your LDAP vendor may support ldaps:// (ldap using SSL) connection strings to connect to your server and a secure port (such as 636) and not require Start-TLS.

For some gritty details see details from the Open LDAP FAQ:
http://www.openldap.org/faq/data/cache/605.html


  The StartTLS extended operation [RFC 2830] is LDAPv3's standard
  mechanism for enabling TLS (SSL) data confidentiality protection. The
  mechanism uses an LDAPv3 extended operation to establish an encrypted
  SSL/TLS connection within an already established LDAP connection.
  While the mechanism is designed for use with TLSv1, most
  implementations will fallback to SSLv3 (and SSLv2) if necessary. 
  
  ldaps:// is a mechanism for establishing an encrypted SSL/TLS
  connection for LDAP. It requires use of separate port, commonly 636.
  Though originally designed for use with LDAPv2 and SSLv2, many
  implementations support its use with LDAPv3 and TLSv1. Although there
  is no technical specification for ldaps:// it is widely used.
  
  ldaps:// is deprecated in favor of Start TLS [RFC2830]. OpenLDAP 2.0
  supports both.
  
  For security reasons the server should be configured
  not to accept SSLv2.


For example at my job they say to use ldaps:// and a secure port when connecting to our LDAP server. They say not to use start-tls. The configuration depends on your LDAP vendor and the version of LDAP you're using.